Lexical-functional grammars (lfg's) were introduced to define the syntax of natural languages. In lfg's, a finite set of attribute-value pairs called an f-structure is associated with each internal node in a derivation tree. For efficient parsing, some subclasses of lfg's were proposed. However, these subclasses have been shown to generate at least one -complete language. In this paper, we introduce a subclass of lfg's called pd-lfg's. In pd-lfg's, an f-structure forms a pushdown stack. For a node v in a derivation tree and at most one specified child v_i of v, the f-structure of v_i is obtained by performing a specified pushdown stack operation on the f-structure of v. We prove the equivalence of the generative capacity of modified head grammars (mhg's) and that of pd-lfg's. Since the languages generated by mhg's are known to be recognizable in O(n⁶) time, the languages generated by pd-lfg's can be recognized in O(n⁶) time.

Recognizable series is a model of a sequential machine. A recognizable series S is represented by a triple (λ,µ,γ), called a linear representation of S, where λ is a row vector of dimension n specifying the initial state, γ is a column vector of dimension n specifying the output at a state, and µ is a morphism from input words to nn matrices specifying the state transition. The output for an input word w is defined as λ(µw) γ, called the coefficient of w in S, and written as (S,w). We present an algorithm which constructs a reduced linear representation of an unknown recognizable series S, with coefficients in a commutative field, using coefficient queries and equivalence queries. The answer to a coefficient query, with a word w, is the coefficient (S, w) of w in S. When one asks an equivalence query with a linear representation (λ,µ,γ), if (λ,µ,γ) is a linear representation of S, yes is returned, and otherwise a word c such that λ (µc) γ(S, c) and the coefficient (S, c) are returned: Such a word c is called a counterexample for the query. For each execution step of the algorithm, the execution time consumed from the initial step to the current step is O(mN ⁴M), where N is the dimension of a reduced linear representation of S, M is the maximum time consumed by a single fundamental operation (addition, subtraction, multiplication or division), and m is the maximum length of counterexamples as answers to equivalence queries returned until that step.

As a generalization of the tree automaton, tree automata with various types of memory are introduced and their relation to context-free grammars with memory is studied. Relations between computation trees of tree automata with memory and derivation trees of context-free grammars with memory are established, and as a consequence, the languages generated by context-free grammars with memory are characterized in terms of the sets of trees recognizable by tree automata with memory. Also various types of traversal of labeled trees recognizable by tree automata with memory are considered.

Several distances between trees have been proposed. However, most of the reports on distances have dealt with rooted and ordered trees. This paper proposes two distances between unrooted and cyclically ordered trees (CO-trees) and their computing methods. A CO-tree is a tree embedded in a plane. These distances are defined based on Tai's mapping (TM) and a strongly structure preserving mapping (SSPM) between CO-trees. The time complexities to compute the distances between two CO-trees T_a and T_b are O_T (N ²_aN ²_b) for the distance based on a TM and O_T(m_am_bN_aN_b) for that on an SSPM, respectively, where m_a(m_b) and N_a(N_b) are the largest degree of a vertex and the number of vertices of T_a(T_b), respectively. The space complexities of both methods are O_s(N_aN_b). Those distances can be applied to the clustering of CO-trees.

This paper presents a novel and successful logic synthesis method for optimizing ternary logic functions of any given number of input variables. A new optimization algorithm to synthesize and minimize an arbitrary ternary logic function of n-input variables can always lead this function to optimal or very close to optimal solution, where [n (n1)/2]1 searches are necessary to achieve the optimal solution. Therefore, the complexity number of this algorithm has been greatly reduced from O(3ⁿ) into O(n²). The advantages of this synthesis and optimization algorithm are: (1) Very easy logic synthesis method. (2) Algorithm complexity is O(n²). (3) Optimal solution can be obtained in very short time. (4) The method can solve the interconnection problems (interconnection delay) of VLSI and ULSI processors, where very fast and parallel operations can be achieved. A transformation method between operational and polynomial domains of ternary logic functions of n-input variables is also discussed. This transformation method is very effective and simple. Design of the circuits of GF(3) operators, addition and multiplication mod-3, have been proposed, where these circuits are composed of Josephson junction devices. The simulation results of these circuits and examples show the following advantages: very good performances, very low power consumption, and ultra high speed switching operation.

A multiple instruction stream-multiple data stream (MIMD) computer is a parallel computer consisting of a large number of identical processing elements. The essential feature that distinguishes one MIMD computer family from another is the interconnection network. In this paper, 2 representative types of interconnection networks are dealt with the chordal ring network and the mesh connected network. A family of regular graphs of degree 3, called chordal rings is presented as a possible candidate for the implementation of a distributed system and for fault-tolerant architectures. The symmetry of graphs makes it possible to determine message routing by using a simple distributed algorithm. Another candidate having the same property is the mesh connected networks. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, there exist algorithms that are more efficient than the best sorting algorithm. One such class is the bit permute complement (BPC) class of permutations. The class of BPC permutations includes many of the frequently occurring permutations such as bit reversal, bit shuffle, bit complement, matrix transpose, etc. In this paper, we evaluate the abilities of the above networks to realize BPC permutations. In this paper, we, first, develop algorithms required 2 token storage registers in each node to realize an arbitrary BPC permutaion in both chordal ring networks and mesh connected networks. We next evaluate the ability to realize BPC permutations in these networks of an arbitrary size by estimating the number of required routing steps.

A new method for the accurate extraction of glottal source parameters is proposed. This method, called Heuristic Analysis-by-Synthesis (HAbS), has been developed specifically to overcome the weaknesses of other methods of glottal source parameter extraction. The specific features of this method are the use of the AbS method for extraction of glottal source and vocal tract parameters, the use of a parametric glottal source model during vocal tract analysis, the use of alternating glottal source and vocal tract analyses, and simultaneous, time-domain analysis of the glottal source parameters and the first formant. This method has been implemented in such a way that user interaction is not required. The performance of the HAbS method is evaluated using both synthetic-speech and natural-speech data. Error is measured in both the time domain and the spectral domain, and the standard deviation of extracted parameter values is computed. In addition, the error in analysis of each glottal-source parameter is computed using synthetic-speech data. In order to assess the accuracy of the HAbS method as compared to other methods, three other methods (LPC, AIF, and AbS) are evaluated using the same data methods of error measurement. From these evaluations, it is clear that the HAbS method yields results that are more accurate than these other methods.

Parallel processing in speech recognition is described, which is carried out at each frame on time axis. We have already proposed a parallel processing algorithm for HMM (Hidden Markov Model)-based speech recognition using Markov Random Fields (MRF). The parallel processing is realized by modeling the hidden state sequence by an MRF and using the Iterated Conditional Modes (ICM) algorithm to estimate the optimal state sequence given an observation sequence and model parameters. However this parallel processing with the ICM algorithm is applicable only to the standard HMM but not to the improved HMM like the linear predictive HMM which takes into account the correlations between nearby observation vectors. In this paper we propose a parallel processing algorithm applicable to the correlation-considered HMM, where a new deterministic relaxation algorithm called the Generalized ICM (GICM) algorithm is used instead of the ICM algorithm for estimation of the optimal state sequence. Speaker independent isolated word recognition experiments show the effectiveness of the proposed parallel processing using the GICM algorithm.

This paper describes a noise resistant algorithm for estimating 3-D rigid motion from optical flow. We first discuss the problem of constructing the objective function to be minimized. If a Gaussian distribution is assumed for the niose, it is well-known that the least-squares minimization becomes the maximum likelihood estimation. However, the use of this objective function makes the minimization procedure more expensive because the program has to go through all the points in the image at each iteration. We therefore introduce an objective function that provides unbiased estimators. Using this function reduces computational costs. Furthermore, since good approximations can be analytically obtained for the function, using them as an initial guess we can apply an iterative minimization method to the function, which is expected to be stable. The effectiveness of this method is demonstrated by computer simulation.

Tomita's parsing method (GLR) is a practical and successful parsing method for natural language. However, one difficulty in the GLR is that interleaved constraint processing of syntax and semantics in parallel is not trivial during parsing, because it uses the precompiled table for a fast real-time parsing. In this paper, we present a method which makes the GLR adaptable to interleaved parsing while making some limitation on its generality. For interleaved parsing, the conflicts of the LR parsing table must be resolved at the parse time. The shift-reduce conflict among the above conflicts is the most serious one for interleaved parsing because of the lack of knowledge for the conflict resolution at the parse time. Therefore, we concentrate on resolving a shift-reduce conflict by introducing a grammar which is called a shift-first LR (k) grammar. Our method for this is that the conflict resolution is delayed by the shift-first strategy which makes an unconditional choice of shift actions in the case of a shift-reduce conflict. Then, a delayed resolution that resolves the conflict, is made. Depending on the decision of the resolution, the pseudo parsing, which parses symbols in the LR parser stack, proceeds. Our experiments showed that our parser is efficient while attaining the interleaved parsing at real time.

Among the problems that face ITS designers, the problem of measuring the student knowledge state after concept learning in order to initially adapt a skill acquisition session according to a student's own necessities is a hard one. Typical approaches are the use of some sort of test to assess the student knowledge and choose an initial set of parameters for a session, or use, regardless the particular necessities of a student, a pre-defined set of initial parameters. We consider the fromer to be disrupting for learning and the latter too simple to deal with the broad possibilities that are faced. It is known that students show different behaviors during concept learning depending on the experience, background and actual understanding (the way a student is understanding a concept) during concept learning. Our approach here is to classify the different behaviors through fuzzy proposition and link them with a student model through fuzzy rules to use in an expert system, and with it, select the most suitable problem-solving strategy for each particular student in order to clear his misunderstandings and facilitate the learning of problem-solving skills. The use of probabilistic reasoning (i.e. Bayesian statistics) instead of fuzzy logic is not suitable for the present situation because of the rigidity and precision of the rules that do not allow a proper manipulation of the vagueness involved in the student behavior. We apply this idea to a circuit analysis ITS where the concept learning session is carried out on a Hypertext environment and the skill acquisition session on an interactive problem-solving environment. By tracing the student use of the Hypertext environment we can know the student behavior and use it as a premise in the fuzzy inference.

We modified the adaptive fuzzy classification algorithm (AFC), which allows fuzzy clusters to grow to meet the demands of a given task during training. Every fuzzy cluster is defined by a reference vector and a fuzzy cluster radius, and it is represented as a shape of hypersphere in pattern space. Any pattern class is identified by overlapping plural hyperspherical fuzzy clusters so that it is possible to approximate complex decision boundaries among pattern classes. The modified AFC was applied to recognize handwritten digits, and performances were shown compared with other neural networks.

A modified deformable model is presented for constructing bijective topology preserving feature maps. The algorithm can solve the optimization problem in the input space as well as that in the output space. A saturating distance function alternative to the Euclid norm is employed to obtain compact space filling maps.