Voir la notice de l'article dans 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.
Mots-clés : 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}, zbl = {1084.68079}, mrnumber = {2059029}, language = {en}, url = {https://geodesic-test.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 - https://geodesic-test.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 https://geodesic-test.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. https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2004004/
Cité par Sources :