Asynchronous and Synchronous Parallel Derivation of Formal Languages

概要

論文の詳細を見る
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 EOL and EIL systems. Languages with restrictions on the number of parallel derivation steps are defined so that a t-time language is the set of strings w derived in t(|w|) or less parallel derivation 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.
1994-05-25