Left-to-right regular languages and two-way restarting automata

Otto, Friedrich

doi:10.1051/ita/2009013

Otto, Friedrich

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 3, pp. 653-665.

Voir la notice de l'article dans Numdam

Résumé

It is shown that the class of left-to-right regular languages coincides with the class of languages that are accepted by monotone deterministic RL-automata, in this way establishing a close correspondence between a classical parsing algorithm and a certain restricted type of analysis by reduction.

MR Zbl

DOI : 10.1051/ita/2009013

Classification : 68Q45
Mots-clés : left-to-right regular grammar, two-way restarting automaton, monotonicity

@article{ITA_2009__43_3_653_0,
     author = {Otto, Friedrich},
     title = {Left-to-right regular languages and two-way restarting automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {653--665},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {3},
     year = {2009},
     doi = {10.1051/ita/2009013},
     zbl = {1176.68107},
     mrnumber = {2541135},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/articles/10.1051/ita/2009013/}
}

TY  - JOUR
AU  - Otto, Friedrich
TI  - Left-to-right regular languages and two-way restarting automata
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2009
SP  - 653
EP  - 665
VL  - 43
IS  - 3
PB  - EDP-Sciences
UR  - https://geodesic-test.mathdoc.fr/articles/10.1051/ita/2009013/
DO  - 10.1051/ita/2009013
LA  - en
ID  - ITA_2009__43_3_653_0
ER  -

%0 Journal Article
%A Otto, Friedrich
%T Left-to-right regular languages and two-way restarting automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2009
%P 653-665
%V 43
%N 3
%I EDP-Sciences
%U https://geodesic-test.mathdoc.fr/articles/10.1051/ita/2009013/
%R 10.1051/ita/2009013
%G en
%F ITA_2009__43_3_653_0

Otto, Friedrich. Left-to-right regular languages and two-way restarting automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 3, pp. 653-665. doi : 10.1051/ita/2009013. https://geodesic-test.mathdoc.fr/articles/10.1051/ita/2009013/

Cité par Sources :