This paper describes recent improvements to Synapse system for incremental learning of general context-free grammars (CFGs) and definite clause grammars (DCGs) from positive and negative sample strings. An important feature of our approach is incremental learning, which is realized by a rule generation mechanism called "bridging" based on bottom-up parsing for positive samples and the search for rule sets. The sizes of rule sets and the computation time depend on the search strategies. In addition to the global search for synthesizing minimal rule sets and serial search, another method for synthesizing semi-optimum rule sets, we incorporate beam search to the system for synthesizing semi-minimal rule sets. The paper shows several experimental results on learning CFGs and DCGs, and we analyze the sizes of rule sets and the computation time.

This paper discusses real-time language recognition by 1-dimensional one-way cellular automata (OCAs) and two-way cellular automata (CAs), focusing on limitations of the parallel computation power. To clarify the limitations, we investigate real-time recognition of cyclic strings of the form uk with u {0,1}+ and k 2. We show a version of pumping lemma for recognizing cyclic strings by OCAs, which can be used for proving that several languages are not recognizable by OCAs in real time. The paper also discusses the real-time language recognition of CAs by prefix and postfix computation, in which every prefix or postfix of an input string is also accepted, if the prefix or postfix is in the language. It is shown that there are languages L Σ+ such that L is not recognizable by OCA in real-time and the reversal of L and the concatenation LΣ* are recognizable by CA in real-time.

This paper describes cellular spaces (or cellular automata) with capabilities of parallel self-reproduction and of parallel universal simulation of other cellular spaces. It is shown that there is a 1-dimensional cellular space U, called a parallel universal simulator, that can simulate any given 1-dimensional cellular space S in the sense that if an initial configuration of U has a coded information of both the local function and an initial configuration of S, then U has the same computation result that S has and the computation time of U is proportional to that of S. Two models of nontrivial parallel self-reproduction are also shown. One model is based on "state-exchange" method, and the other is based on a fixed point program of the parallel universal simulator.

This paper discusses the asynchronous and synchronous parallel derivation of languages based on standard formal grammars. Some of the synchronous languages defined in this paper are essentially equivalent to the languages of E0L and EIL systems. Languages with restrictions on the number of parallel derivation steps are difined so that a t-time language is the set of strings w derived in t(w) or less parallel derivatio steps, where t(n) is an integer function. the properties of asynchronous derivation are generally discussed to clarify their conditions so that the derivation results are independent of the order in which productions are applied. It is shown that: (1) Any context sensitive grammar (CSG) G can be transformed into a CSG G such that the language generated by synchronous derivation in G is equal to that generated by asynchronous derivation in G , and vice versa; (2) Any regular language is a log-time context free language (CFL); (3) The class of CFLs is incomparable with that of log-time CSLs; and (4) If there is a bounded cellular automaton recognizing any language L in time T(n), then L is an O(T(n))-time CSL.