On the synchronization in parallel communicating grammar systems (Q1323329)

The power of various types of synchronization in parallel communication grammar systems is investigated. These systems were introduced by the author and \textit{L. Santean} [Ann. Univ. Bucuresti, Series Matem.-Inform., 38, No. 2, 55-63 (1989; Zbl 0749.68048)] and consist of more Chomsky grammars working together for generating one language. (Details can be found in the survey \textit{L. Santean} [Parallel communicating systems, Bull. EATCS, 42, 160-171 (1990; Zbl 0745.68070)] and in the forthcoming monograph Grammar systems, by \textit{E. Csuhaj-Varju}, \textit{J. Dassow}, \textit{J. Kelemen} and the author, to be published by Gordon and Breach, London.) When the grammars are not synchronized (there is no universal clock at the level of the system, imposing that one rule is used in each time unit by each grammar), such systems proves to be weaker than the synchronized ones (a pumping lemma is used in this aim). Further synchronizing restrictions are introduced (added to the basic synchronization by a universal clock) and their effect on the generative capacity of grammar systems is examined.