| Issue |
RAIRO-Theor. Inf. Appl.
Volume 38, Number 1, January-March 2004
|
|
|---|---|---|
| Page(s) | 69 - 88 | |
| DOI | https://doi.org/10.1051/ita:2004004 | |
| Published online | 15 March 2004 | |
On the equivalence of linear conjunctive grammars and trellis automata
School of Computing,
Queen's University, Kingston, Ontario, Canada; okhotin@cs.queensu.ca.
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.