On the power of cooperation: A regular representation of recursively enumerable languages (Q1176482)

A cooperating distributed grammar system (CDGS), as introduced by \textit{E. Csuhaj-Varju} and \textit{J. Dassow} [J. Inform. Process. Cybern. EIK 26, 49-63 (1990)] is a construct \(\gamma=(N,T,G_ 1,\dots\), \(G_ n,S)\), where \(N\), \(T\) are nonterminal and terminal vocabularies, \(S\in N\) and \(G_ i=(N_ i,T_ i,S_ i,P_ i)\) are grammars with \(N_ i\subseteq N\), \(T_ i\subseteq N\cup T\), \(1\leq i\leq n\), \(S=S_ i\) for some \(i\). The derivation starts from \(S\); the components of \(\gamma\) work in turn, every enabled component rewrites the current sentential form as long as it can. The paper proves that every recursively enumerable language can be generated by a CDGS with two components, which are in fact conditional regular grammars, with condition strings of length at most two (a conditional rule has the form \(w: A\to x\), with \(w\) a string and \(A\to x\) a usual rewriting rule; \(A\to x\) is used for rewriting only strings containing \(w\) as a substring). The proof is based on a characterization of recursively enumerable languages by \textit{V. Geffert} [Theor. Comput. Sci. 62, 235-249 (1988)].