Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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 : 10.1051/ita:2004004
Classification : 68Q01, 68Q42, 68Q70, 68Q80
Keywords: 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},
     mrnumber = {2059029},
     zbl = {1084.68079},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2004004/}
}
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
SP  - 69
EP  - 88
VL  - 38
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2004004/
DO  - 10.1051/ita:2004004
LA  - en
ID  - ITA_2004__38_1_69_0
ER  - 
%0 Journal Article
%A Okhotin, Alexander
%T On the equivalence of linear conjunctive grammars and trellis automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2004
%P 69-88
%V 38
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2004004/
%R 10.1051/ita:2004004
%G en
%F ITA_2004__38_1_69_0
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

Cité par Sources :