Left-to-right regular languages and two-way restarting automata
Otto, Friedrich
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009), p. 653-665 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2009-01-01
DOI : https://doi.org/10.1051/ita/2009013
Classification:  68Q45 
@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},
     volume = {43},
     year = {2009},
     pages = {653-665},
     doi = {10.1051/ita/2009013},
     mrnumber = {2541135},
     zbl = {1176.68107},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 653-665. doi : 10.1051/ita/2009013. http://gdmltest.u-ga.fr/item/ITA_2009__43_3_653_0/

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

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

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

[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 319413 | Zbl 0253.68014

[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 0977.68570

[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 693068 | Zbl 0507.68044

[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 1459184

[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 1737858 | Zbl 0942.68064

[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 2062454 | Zbl 1056.68095

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

[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 2187270 | Zbl 1132.68450

[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 1142.68423

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

[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 935255 | Zbl 0652.68093

[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 2260999 | Zbl pre05148731

[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 2028887

[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 2126360 | Zbl 1075.68046

[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 2053874 | Zbl 1037.68088

[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 1052.68628

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

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