On the power of cooperation: A regular representation of recursively enumerable languages (Q1176482)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the power of cooperation: A regular representation of recursively enumerable languages |
scientific article |
Statements
On the power of cooperation: A regular representation of recursively enumerable languages (English)
0 references
25 June 1992
0 references
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)].
0 references
cooperating distributed grammar system
0 references
recursively enumerable language
0 references
0 references