On the equivalence of linear conjunctive grammars and trellis automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) no. 1, pp. 69-88.

This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence of several other formal systems, including a certain restricted class of Turing machines and a certain type of language equations, thus giving further evidence for the importance of the language family they all generate.

DOI : https://doi.org/10.1051/ita:2004004
Classification : 68Q01,  68Q42,  68Q70,  68Q80
Mots clés : conjunctive grammar, trellis automaton, cellular automaton, language equation, Turing machine
@article{ITA_2004__38_1_69_0,
author = {Okhotin, Alexander},
title = {On the equivalence of linear conjunctive grammars and trellis automata},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {69--88},
publisher = {EDP-Sciences},
volume = {38},
number = {1},
year = {2004},
doi = {10.1051/ita:2004004},
zbl = {1084.68079},
mrnumber = {2059029},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2004004/}
}
Okhotin, Alexander. On the equivalence of linear conjunctive grammars and trellis automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) no. 1, pp. 69-88. doi : 10.1051/ita:2004004. http://www.numdam.org/articles/10.1051/ita:2004004/

[1] J. Autebert, J. Berstel and L. Boasson, Context-Free Languages and Pushdown Automata. Handbook of Formal Languages 1 (1997) 111-174. | MR 1469995 | Zbl 0900.68286

[2] C. Choffrut and K. Culik Ii, On real-time cellular automata and trellis automata. Acta Inform. 21 (1984) 393-407. | MR 767316 | Zbl 0534.68039

[3] N. Chomsky and M.P. Schützenberger, The algebraic theory of context-free languages. Computer programming and formal systems (1963) 118-161. | MR 152391 | Zbl 0148.00804

[4] K. Culik Ii, J. Gruska and A. Salomaa, Systolic trellis automata (I, II). Int. J. Comput. Math. 15 (1984) 195-212; 16 (1984) 3-22; preliminary version in: Research Rep. CS-81-34, Dept. of Computer Sci., U. of Waterloo, Canada (1981). | Zbl 0571.68042

[5] K. Culik Ii, J. Gruska and A. Salomaa, Systolic trellis automata: stability, decidability and complexity. Inform. Control 71 (1986) 218-230. | Zbl 0626.68048

[6] C. Dyer, One-way bounded cellular automata. Inform. Control 44 (1980) 261-281. | MR 574487 | Zbl 0442.68082

[7] O.H. Ibarra and S.M. Kim, Characterizations and computational complexity of systolic trellis automata. Theoret. Comput. Sci. 29 (1984) 123-153. | MR 742405 | Zbl 0536.68048

[8] O.H. Ibarra, S.M. Kim and S. Moran, Sequential machine characterizations of trellis and cellular automata and applications. SIAM J. Comput. 14 (1985) 426-447. | MR 784748 | Zbl 0574.68044

[9] A. Okhotin, Conjunctive grammars. J. Autom. Lang. Comb. 6 (2001) 519-535; preliminary version in: Pre-proceedings of DCAGRS 2000, London, Ontario, Canada, July 27-29 (2000). | MR 1897299 | Zbl 1004.68082

[10] A. Okhotin, Conjunctive grammars. and systems of language equations. Programming and Computer Software 28 (2002) 243-249. | MR 2023633 | Zbl 1036.68063

[11] A. Okhotin, On the closure properties of linear conjunctive languages. Theoret. Comput. Sci. 299 (2003) 663-685. | MR 1973171 | Zbl 1042.68069

[12] A. Okhotin, Whale Calf, a parser generator for conjunctive grammars, in Implementation and Application of Automata, Proc. CIAA 2002, Tours, France, July 3-5, 2002. Lect. Notes Comput. Sci. (2002). 2608 213-220. | Zbl 1033.68579

[13] A. Okhotin, Boolean grammars, in Developments in Language Theory, Proc. DLT 2003, Szeged, Hungary, July 7-11, 2003. Lect. Notes Comput. Sci. 2710 (2003) 398-410. | MR 2054381 | Zbl 1037.68071

[14] A.R. Smith Iii, Cellular automata and formal languages, in Proc. 11th IEEE Annual Sympo. Switching and Automata Theory (1970) 216-224.

[15] A.R. Smith Iii, Real-time language recognition by one-dimensional cellular automata. J. Comput. Syst. Sci. 6 (1972) 233-252. | MR 309383 | Zbl 0268.68044

[16] V. Terrier, On real-time one-way cellular array. Theoret. Comput. Sci. 141 (1995) 331-335. | MR 1323161 | Zbl 0873.68114