On the equivalence of linear conjunctive grammars and trellis automata
School of Computing,
Queen's University, Kingston, Ontario, Canada; firstname.lastname@example.org.
Accepted: 15 January 2004
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.
Mathematics Subject Classification: 68Q01 / 68Q42 / 68Q70 / 68Q80
Key words: Conjunctive grammar / trellis automaton / cellular automaton / language equation / Turing machine.
© EDP Sciences, 2004