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.

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.

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},
     mrnumber = {2541135},
     zbl = {1176.68107},
     language = {en},
     url = {http://www.numdam.org/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  - http://www.numdam.org/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 http://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita/2009013/

[1] T.P. Baker, Extending lookahead for LR parsers. J. Comput. System. Sci. 22 (1981) 243-259. | MR | Zbl

[2] M. Bermudez and K. Schimpf, Practical arbitrary lookahead LR parsing. J. Comput. System. Sci. 41 (1990) 230-250. | MR | Zbl

[3] G. Buntrock and F. Otto, Growing context-sensitive languages and Church-Rosser languages. Inform. Comput. 141 (1998) 1-36. | MR | Zbl

[4] K. Čulik Ii and R. Cohen, LR-regular grammars - an extension of LR(k) grammars. J. Comput. System. Sci. 7 (1973) 66-96. | MR | Zbl

[5] J. Farré and J. Fortes Gálvez, A bounded graph-connect construction for LR-regular parsers, in Proc. Compiler Construction, CC 2001. Lect. Notes Comput. Sci. 2027 (2001) 244-258. | Zbl

[6] S. Heilbrunner, A metatheorem for undecidable properties of formal languages and its application to LRR and LLR grammars and languages. Theoret. Comput. Sci. 23 (1983) 49-68. | MR | Zbl

[7] P. Jančar, F. Mráz, M. Plátek and J. Vogel, Restarting automata, in Proc. FCT 1995. Lect. Notes Comput. Sci. 965 (1995) 283-292. | MR

[8] P. Jančar, F. Mráz, M. Plátek and J. Vogel, On monotonic automata with a restart operation. J. Autom. Lang. Comb. 4 (1999) 287-311. | MR | Zbl

[9] T. Jurdziński and K. Loryś, Church-Rosser languages vs. UCFL, in Proc. ICALP 2002. Lect. Notes Comput. Sci. 2380 (2002) 147-158. | MR | Zbl

[10] T. Jurdziński and F. Otto, Shrinking restarting automata. Int. J. Found. Comput. Sci. 18 (2007) 361-385. | MR | Zbl

[11] T. Jurdziński, F. Mráz, F. Otto and M. Plátek, Monotone deterministic RL-automata don't need auxiliary symbols, in Proc. DLT 2005. Lect. Notes Comput. Sci. 3572 (2005) 284-295. | MR | Zbl

[12] T. Jurdziński, F. Mráz, F. Otto and M. Plátek, Degrees of non-monotonicity for restarting automata. Theoret. Comput. Sci. 369 (2006) 1-34. | Zbl

[13] M. Kutrib and A. Malcher, When Church-Rosser becomes context-free. Int. J. Found. Comput. Sci. 18 (2007) 1293-1302. | MR

[14] C. Lautemann, One pushdown and a small tape, in Dirk Siefkes zum 50. Geburtstag, edited by K.W. Wagner, Technische Universität Berlin and Universität Augsburg (1988) 42-47.

[15] R. Mcnaughton, P. Narendran and F. Otto, Church-Rosser Thue systems and formal languages. J. ACM 35 (1988) 324-344. | MR | Zbl

[16] H. Messerschmidt, CD-Systems of Restarting Automata. Doctoral Dissertation, Fachbereich Elektrotechnik/Informatik, Universität Kassel (2008).

[17] H. Messerschmidt and F. Otto, On nonforgetting restarting automata that are deterministic and/or monotone, in Proc. CSR 2006. Lect. Notes Comput. Sci. 3967 (2006) 247-258. | MR

[18] H. Messerschmidt and H. Stamer, Restart-Automaten mit mehreren Restart-Zuständen, in Proc. Workshop “Formale Methoden in der Linguistik” und 14. Theorietag “Automaten und Formale Sprachen”, edited by H. Bordihn, Institut für Informatik, Universität Potsdam (2004) 111-116.

[19] P. Narendran, Church-Rosser and Related Thue Systems. Ph.D. thesis, Rensselaer Polytechnic Institute, Troy, New York (1984).

[20] G. Niemann and F. Otto, Further results on restarting automata, in Proc. Words, Languages and Combinatorics III, edited by M. Ito and T. Imaoka, World Scientific, Singapore (2003) 353-369. | MR

[21] G. Niemann and F. Otto, The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Inform. Comput. 197 (2005) 1-21. | MR | Zbl

[22] F. Otto, Restarting automata and their relations to the Chomsky hierarchy, in Proc. DLT 2003. Lect. Notes Comput. Sci. 2710 (2003) 55-74. | MR | Zbl

[23] F. Otto, Restarting automata, in Recent Advances in Formal Languages and Applications, edited by Z. Ésik, C. Martin-Vide and V. Mitrana. Studies in Computational Intelligence 25 (2006) 269-303.

[24] M. Plátek, Two-way restarting automata and j-monotonicity, in Proc. SOFSEM 2001. Lect. Notes Comput. Sci. 2234 (2001) 316-325. | Zbl

[25] B. Seité, A YACC extension for LRR grammar parsing. Theoret. Comput. Sci. 52 (1987) 91-143. | MR | Zbl

[26] T. Szymanski and J. Williams, Noncanonical extensions of bottom-up parsing techniques. SIAM J. Comput. 5 (1976) 231-250. | MR | Zbl

Cité par Sources :