# On the equivalence of linear conjunctive grammars and trellis automata

RAIRO - Theoretical Informatics and Applications (2010)

- 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 38.1 (2010): 69-88. <http://eudml.org/doc/92734>.

@article{Okhotin2010,

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},

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

language = {eng},

month = {3},

number = {1},

pages = {69-88},

publisher = {EDP Sciences},

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

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

volume = {38},

year = {2010},

}

TY - JOUR

AU - Okhotin, Alexander

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

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

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/92734

ER -

## References

top- J. Autebert, J. Berstel and L. Boasson, Context-Free Languages and Pushdown Automata. Handbook of Formal Languages1 (1997) 111-174.
- C. Choffrut and K. Culik II, On real-time cellular automata and trellis automata. Acta Inform.21 (1984) 393-407.
- N. Chomsky and M.P. Schützenberger, The algebraic theory of context-free languages. Computer programming and formal systems (1963) 118-161.
- 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).
- K. Culik II, J. Gruska and A. Salomaa, Systolic trellis automata: stability, decidability and complexity. Inform. Control71 (1986) 218–230.
- C. Dyer, One-way bounded cellular automata. Inform. Control44 (1980) 261-281.
- O.H. Ibarra and S.M. Kim, Characterizations and computational complexity of systolic trellis automata. Theoret. Comput. Sci.29 (1984) 123-153.
- 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.
- 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).
- A. Okhotin, Conjunctive grammars. and systems of language equations. Programming and Computer Software28 (2002) 243-249.
- A. Okhotin, On the closure properties of linear conjunctive languages. Theoret. Comput. Sci.299 (2003) 663-685.
- 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.
- 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.
- A.R. Smith III, Cellular automata and formal languages, in Proc. 11th IEEE Annual Sympo. Switching and Automata Theory (1970) 216-224.
- A.R. Smith III, Real-time language recognition by one-dimensional cellular automata. J. Comput. Syst. Sci.6 (1972) 233-252.
- V. Terrier, On real-time one-way cellular array. Theoret. Comput. Sci.141 (1995) 331-335.

## NotesEmbed ?

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