We introduce automatic procedures for generating and verifying sufficient correctness properties of synchronous processors. The targeted circuits are synchronous array processors designed from localized, highly regular data dependency graphs (DDGs). The specification, in the form of a DDG, is viewed as a maximally parallel circuit. The implementation, on the other hand, is a (partially) serialized circuit. Since these circuits are not equivalent from an automata-theoretic viewpoint, we define the correctness of the implementation against the specification to mean that a certain relation (called the β-relation) holds between the two. We use a compositional approach to decouple the verification of the control circuitry from that of the data path, thereby gaining efficiency. An array processor in isolation may not have a definite flow of control, because control may reside in the data stream. Therefore, for the purpose of verification, we construct an auxiliary machine, which keeps a timing reference and generates control signals abstracted from a typical data stream. Sufficient correctness conditions are expressed as past-tense computation tree logic (CTL) formulae and verified by CTL model-checking procedures. Experimental results of the verification of a matrix multiplication array and a Gaussian elimination array are presented.

A new applicative design language is proposed for developing generators of data-path modules from hardware algorithms. The language includes a set of primitives that represent placement operations, parameterized cells, routing patterns and a set of transformation rules specifying modifications of the module topology without changing its functionality. Using the language, a hardware algorithm designer can easily define both the topological and geometrical specifications of module generation directly at the functional level without engaged in the layout details. A sketch of the language and an example of module design with the language is presented.

This system called COKIS automatically extracts knowledge about C functions from the UNIX on-line manual by using its description paragraph and the user can interactively inquire to the system in order to know about UNIX C functions. The idea is motivated on the one side to free users from being involved in an exhaustive knowledge acquisition in the past, and to examine problems in understanding knowledge itself on the other. We propose Memory Processor which is implemented to realize extracting knowledges from corpus and processing dialogues in the inquiry system at the same modules.

In using a natural language database interface (NLI) to access the contents of a databese, the user queries may contain terms that do not appear at all in both the NLI lexicon and the database. A friendly NLI should not reject user queries with unknown terms, but should be able to handle them, and should be able to learn new lexical items. Such capability increases the usefulness of the NLI, and allows the NLI to more cover the domain of the underlying database. Therefore, a technique to handle unknown terms is decisive in designing a friendly NLI. In this work, we discuss a method that would allow a NLI to identify the meanings of unknown database field values, and terms that are exceeding the conceptual coverage of the database, in the user queries, by engaging the user in clarification dialogues based on a database-domain hierarchy. It will be shown that the method enables the NLI lexicon to learn new lexical items at run time while the clarification dialogues, and it may provide the necessary information for generating informative answers to some particular failing user queries. Moreover, the method is an efficient means to handle queries with insufficience contextual cues. The examples throughout this work are drawn from FIFA 90, an experimental NLI to a soccer database.

Some problems in formal language theory are considered and are shown to be deterministic exponential time complete. They include the problems for a given context-free grammar G, a nondeterministic finite automaton M, a deterministic pushdown automaton MD, of determining whether L(G)L(M), and whether L(MD)L(M). Polynomial time reductions are presented from the pebble game problem, known to be deterministic exponential time complete, to each of these problems.

Given an integer N, it is easy to determine whether or not N is prime, because a set of primes is in LPP. Then given a composite number N, is it easy to determine whether or not N is of a specified form? In this paper, we consider a subset of odd composite numbers +1MOD4 (resp. +3MOD4), which is a subset of odd composite numbers consisting of prime factors congruent to 1 (resp. 3) modulo 4, and show that (1) there exists a four move (blackbox simulation) perfect ZKIP for the complement of +1MOD4 without any unproven assumption; (2) there exists a five move (blackbox simulation) perfect ZKIP for +1MOD4 without any unproven assumption; (3) there exists a four move (blackbox simulation) perfect ZKIP for +3MOD4 without any unproven assumption; and (4) there exists a five move (blackbox simulation) statistical ZKIP for the complement of +3MOD4 without any unproven assumption. To the best of our knowledge, these are the first results for a language L that seems to be not random self-reducible but has a constant move blackbox simulation perfect or statistical ZKIP for L and without any unproven assumption.

This paper discusses the problems facing spoken dialogue processing and the prospects for future improvements. Research on elemental topics like speech recognition, speech synthesis and language understanding has led to improvements in the accuracy and sophistication of each area of study. First, in order to handle a spoken dialogue, we show the necessity for information exchanges between each area of processing as seen through the analysis of spoken dialogue characteristics. Second, we discuss how to integrate those processes and show that the memory-basad approach to spontaneous speech interpretation offers a solution to the problem of process integration. The key to this is setting up a mental state affected by both speech and linguistic information. Finally, we discuss how those mental states are structured and a method for constructing them.

We studied the manner of clarification and verification in real dialogs and developed a spoken dialog system that can cope with the disambiguation of meanings of user input utterances. We analyzed content, query types and responses of human clarification queries. In human-human communications, ten percent of all sentences are concerned with meaning clarification. Therefore, in human-machine communications, we believe it is important that the machine verifies ambiguities occurring in dialog processing. We propose an architecture for a dialog system with this capability. Also, we have investigated the source of ambiguities in dialog processing and methods of dialog clarification for each part of the dialog system.

In speech recognition systeme dealing with unlimited vocabulary and based on stochastic language models, when the target recognition task is changed, recognition performance decreases because the language model is no longer appropriate. This paper describes two approaches for adapting a specific/general syllable trigram model to a new task. One uses a amall amount of text data similar to the target task, and the other uses supervised learning using the most recent input phrases and similar text. In this paper, these adaptation methods are called preliminary learning" and successive learning", respectively. These adaptation are evaluated using syllable perplexity and phrase recognition rates. The perplexity was reduced from 24.5 to 14.3 for the adaptation using 1000 phrases of similar text by preliminary learning, and was reduced to 12.1 using 1000 phrases including the 100 most recent phrases by successive learning. The recognition rates were also improved from 42.3% to 51.3% and 52.9%, respectively. Text similarity for the approaches is also studied in this paper.

CFGs (context-free grammars) with various types of memory are introduced and their generative capacities are investigated. For an automata-theoretic characterization, a new type of automaton called partitioning automaton is introduced and it is shown that the class of languages generated by CFGs with memory type X is equal to the class of languages accepted by partitioning automata of type X.

This paper describes a new method for verifying designs at the RTL with respect to their specifications at the functional level. The base of the verification method shown here is the translation of the specification and design representations to graph models, where the descriptions common to both representations have a symbolic representation. These symbol labeled graphs are then simplified and, by solving the all node-pair path expression problem for them, a pair of regular expressions is obtained for every two nodes in the graphs. The first regular expression in each pair represents the flow of control and the second one the flow of data between the corresponding nodes. The process of verification is carried out by checking whether or not every pair of regular expressions of the specification has a corresponding pair in the design.

Although individual segments of a natural language such as words have different importance on human interpretation of the meaning, every segment has been uniformly protected by an error-correcting code. If the importance of individual segments is defined by considering their meaning in the sentence, we can adaptively control the level of error-protection for each segment according to its importance in order to reduce errors on human interpretation of the meaning. In this paper, we propose an error-control scheme based on the varying importance of each word. We first introduce a method which determines the importance of each word and then propose an error-control scheme in which several error-correcting codes are alternately used to protect each word according to its importance. Probablity of semantic errors, that is, errors on human interpretation of the meaning, is defined and used as a criterion in mapping error-correcting codes to words possessing different importance. We theoretically formalize the problem of obtaining an optimum mapping which minimizes the probability of semantic errors under some constraint. Given a certain probability distribution of the importance of words and set of error-correcting codes, we can derive the optimum mapping. The proposed error-controlling scheme is theoretically evaluated by comparing its probability of semantic errors with that of a conventional scheme in which every word is uniformly protected by a single error-correcting code. Results show that the proposed scheme can considerably raduce the probability of semantic errors while retaining the same average transmission rate or redundancy.

Lexical-Functional Grammars (LFG's) were introduced to define the syntax of natural languages. In LFG's, each node of a derivation tree has some attributes. An LFG G consists of a context-free grammar (cfg) G0 called the underlying cfg of G and a description Pfs of constraints between the values of the attributes. Pfs can specify (1) constraints between the value of an attribute of a node and those of its children, and (2) constraints between the value of an attribute of a node called a controller and that of a node called its controllee. RLFG's were introduced as a subclass of LFG's. In RLFG's, only constraints between the value of an attribute of a node and those of its children can be specified. It is shown in this paper that the class of languages generated by RLFG's is equal to the class of recursively enumerable languages. Some restrictions on LFG's were proposed for the purpose of efficient parsing. Among them are (1) the condition called a valid derivation, and (2) the condition that the underlying cfg is cycle-free. For an RLFG G, if the production rules of the underlying cfg of G are of the form AaB or Aa for nonterminal symbols A, B and a terminal symbol a, then G is called an R-RLFG. Every R-RLFG satisfies the above restriction (1) and (2). It is also shown in this paper that the class of languages generated by R-RLFG's contains an NP-hard language, which means that parsing in deterministic polynomial time of LFG's is impossible in general (unless PNP) even if the above restrictions (1) and (2) are satisfied.

This paper designs and evaluates highly parallel VLSI processors for real time 2-D state-space digital filters using hierarchical behavioral description language and synthesizer. The architecture of the 2-D state-space digital filtering system is a linear systolic array of homogeneous VLSI processors, each of which consists of eight processing elements (PEs) executing 1-D state-space digital filtering with multi-input and multi-output. Hierarchical behavioral description language and synthesizer are adopted to design and evaluate PE's and the VLSI processors. One 16 bit fixed-point PE executing a (4, 4)-th order 2-D state-space digital filtering is described on the basis of distributed arithmetic in about 1,200 steps by the description language and is composed of 15 K gates in terms of 2 input NAND gate. One VLSI processor which is a cascade connection of eight PEs is composed of 129 K gates and can be integrated into one 1515 [mm2] VLSI chip using 1 µm CMOS standard cell. The 2-D state-space digital filtering system composed of 128 VLSI processors at 25 MHz clock can execute a 1,0241,024 image in 1.47 [msec] and thus can be applied to real-time conventional video signal processing.

A pattern is a finite string of constant symbols and variable symbols. The language of a pattern is the set of all strings obtained by substituting any nonnull constant string for each variable symbol in the pattern. The class of pattern languages was introduced by Angluin in 1979 as a concrete class which is inferable from positive data. In this paper, we consider the decision problem whether for given two patterns there is a containment relation between their languages, which was posed by Angluin and its decidability remains open. We give some sufficient conditions to make this problem decidable. We also introduce the notions of generalizations and minimal generalizations common to a set of patterns. We characterize the above open problem using the minimal generalization.

Parallel multiple context-free grammars (pmcfg's) and multiple context-free grammars (mcfg's) were introduced as extensions of context-free grammars to describe the syntax of natural languages. Pmcfg's and mcfg's deal with tuples of strings, and it has been shown that the universal recognition problem for mcfg's is EXP-POLY time-complete where the universal recognition problem is the problem to decide whether G generates w for a given grammar G and string w. In this paper, the universal recognition problems for the class of pmcfg's and for the subclass of pmcfg's with the information-lossless condition are shown to be EXP-POLY time-complete and PSPACE-complete, respectively. It is also shown that the problems for pmcfg's and for mcfg's with a bounded dimension are both -complete and those for pmcfg's and for mcfg's with a bounded degree are both -complete. As a corollary, the problem for modified head grammars introduced by Vijay-Shanker, et al. to define the syntax of natural languages is shown to be in deterministic polynomial time.

In this paper, we consider the polynomial time inferability from positive data for unions of two tree pattern languages. A tree pattern is a structured pattern known as a term in logic programming, and a tree pattern language is the set of all ground instances of a tree pattern. We present a polynomial time algorithm to find a minimal union of two tree pattern languages containing given examples. Our algorithm can be considered as a natural extension of Plotkin's least generalization algorithm, which finds a minimal single tree pattern language. By using this algorithm, we can realize a consistent and conservative polynomial time inference machine that identifies unions of two tree pattern languages from positive data in the limit.

Spoken language systems such as speech-to-speech dialog translation systems have been gaining more attention in recent years. These systems require full integration of speech recognition and natural language understanding. This paper presents an efficient parsing algorithm that integrates the search problems of speech processing and language processing. The parsing algorithm we propose here is regarded as an extension of the finite-state-network directed, one-pass search algorithm to one directed by a context-free grammar with retention of the time-synchronous procedure. The extended search algorithm is used to find approximately globally optimal sentence hypotheses; it does not have overhead which exists in, for example, hierarchical systems based on the lattice parsing approach. The computational complexity of this search algorithm is proportional to the length of the input speech. As the search process in the speech recognition can directly take account of the predictive information in the sentence parsing, this framework can be extended to sopken language systems which deal with dynamically varying constraints in dialogue situations.

In this paper, we deal with inductive inference of an indexed family of recursive languages. We give two sufficient conditions for inductive inferability of an indexed family from positive data, each of which does not depend on the indexing of the family. We introduce two notions of finite cross property for a class of languages and a pair of finite tell-tales for a language. The former is a generalization of finite elasticity due to Wright and the latter consists of two finite sets of strings one of which is a finite tell-tale introduced by Angluin. The main theorem in this paper is that if any language of a class has a pair of finite tell-tales, then the class is inferable from positive data. Also, it is shown that any language of a class with finite cross property has a pair of finite tell-tales. Hence a class with finite cross property is inferable from positive data. Further-more, it is proved that a language has a finite tell-tale if and only if there does not exist any infinite cross sequence of languages contained in the language.

Resolving ambiguities in interpreting the user's utterances is one of the most fundamental problems in the development of a question-answering system. The process of disambiguating interpretations requires knowledge and inference functions on an objective task field. This paper describes a framework for understanding conversational language, using the multi-paradigm knowledge representation (frames" and rules") which represents concept hierarchy and causal relationships for an objective field. Knowledge of the objective field is used in the process to interpret input sentences as a model for the objective world. In interpreting sentences, a procedure judges preferences for interpretation candidates by identifying causal relationship with messages in the preceding context, where the causal relationship is used to supplement some shortage of information and to give either an affirmative or a negative explanation to the interpretation. The procedure has been implemented in an experimental question-answering system, whose current task is consultation in operating an electronic device. The experimental results are shown for a concrete problem involving resolving anaphoric references, and characteristics of the knowledge processing system are discussed.