# On the equivalence of linear conjunctive grammars and trellis automata

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2004)

- Volume: 38, Issue: 1, page 69-88
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topOkhotin, Alexander. "On the equivalence of linear conjunctive grammars and trellis automata." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 38.1 (2004): 69-88. <http://eudml.org/doc/244936>.

@article{Okhotin2004,

abstract = {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.},

author = {Okhotin, Alexander},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {conjunctive grammar; trellis automaton; cellular automaton; language equation; Turing machine},

language = {eng},

number = {1},

pages = {69-88},

publisher = {EDP-Sciences},

title = {On the equivalence of linear conjunctive grammars and trellis automata},

url = {http://eudml.org/doc/244936},

volume = {38},

year = {2004},

}

TY - JOUR

AU - Okhotin, Alexander

TI - On the equivalence of linear conjunctive grammars and trellis automata

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2004

PB - EDP-Sciences

VL - 38

IS - 1

SP - 69

EP - 88

AB - 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.

LA - eng

KW - conjunctive grammar; trellis automaton; cellular automaton; language equation; Turing machine

UR - http://eudml.org/doc/244936

ER -

## References

top- [1] J. Autebert, J. Berstel and L. Boasson, Context-Free Languages and Pushdown Automata. Handbook of Formal Languages 1 (1997) 111-174. Zbl0900.68286MR1469995
- [2] C. Choffrut and K. Culik II, On real-time cellular automata and trellis automata. Acta Inform. 21 (1984) 393-407. Zbl0534.68039MR767316
- [3] N. Chomsky and M.P. Schützenberger, The algebraic theory of context-free languages. Computer programming and formal systems (1963) 118-161. Zbl0148.00804MR152391
- [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). Zbl0571.68042
- [5] K. Culik II, J. Gruska and A. Salomaa, Systolic trellis automata: stability, decidability and complexity. Inform. Control 71 (1986) 218–230. Zbl0626.68048
- [6] C. Dyer, One-way bounded cellular automata. Inform. Control 44 (1980) 261-281. Zbl0442.68082MR574487
- [7] O.H. Ibarra and S.M. Kim, Characterizations and computational complexity of systolic trellis automata. Theoret. Comput. Sci. 29 (1984) 123-153. Zbl0536.68048MR742405
- [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. Zbl0574.68044MR784748
- [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). Zbl1004.68082MR1897299
- [10] A. Okhotin, Conjunctive grammars. and systems of language equations. Programming and Computer Software 28 (2002) 243-249. Zbl1036.68063MR2023633
- [11] A. Okhotin, On the closure properties of linear conjunctive languages. Theoret. Comput. Sci. 299 (2003) 663-685. Zbl1042.68069MR1973171
- [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. Zbl1033.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. Zbl1037.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. Zbl0268.68044MR309383
- [16] V. Terrier, On real-time one-way cellular array. Theoret. Comput. Sci. 141 (1995) 331-335. Zbl0873.68114MR1323161

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.