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.
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] , Extending lookahead for LR parsers. J. Comput. System. Sci. 22 (1981) 243-259. | MR | Zbl
[2] and , Practical arbitrary lookahead LR parsing. J. Comput. System. Sci. 41 (1990) 230-250. | MR | Zbl
[3] and , Growing context-sensitive languages and Church-Rosser languages. Inform. Comput. 141 (1998) 1-36. | MR | Zbl
[4] and , LR-regular grammars - an extension of LR() grammars. J. Comput. System. Sci. 7 (1973) 66-96. | MR | Zbl
[5] and , 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] , 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] , , and , Restarting automata, in Proc. FCT 1995. Lect. Notes Comput. Sci. 965 (1995) 283-292. | MR
[8] , , and , On monotonic automata with a restart operation. J. Autom. Lang. Comb. 4 (1999) 287-311. | MR | Zbl
[9] and , Church-Rosser languages vs. UCFL, in Proc. ICALP 2002. Lect. Notes Comput. Sci. 2380 (2002) 147-158. | MR | Zbl
[10] and , Shrinking restarting automata. Int. J. Found. Comput. Sci. 18 (2007) 361-385. | MR | Zbl
[11] , , and , Monotone deterministic RL-automata don't need auxiliary symbols, in Proc. DLT 2005. Lect. Notes Comput. Sci. 3572 (2005) 284-295. | MR | Zbl
[12] , , and , Degrees of non-monotonicity for restarting automata. Theoret. Comput. Sci. 369 (2006) 1-34. | Zbl
[13] and , When Church-Rosser becomes context-free. Int. J. Found. Comput. Sci. 18 (2007) 1293-1302. | MR
[14] , 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] , and , Church-Rosser Thue systems and formal languages. J. ACM 35 (1988) 324-344. | MR | Zbl
[16] , CD-Systems of Restarting Automata. Doctoral Dissertation, Fachbereich Elektrotechnik/Informatik, Universität Kassel (2008).
[17] and , On nonforgetting restarting automata that are deterministic and/or monotone, in Proc. CSR 2006. Lect. Notes Comput. Sci. 3967 (2006) 247-258. | MR
[18] and , 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] , Church-Rosser and Related Thue Systems. Ph.D. thesis, Rensselaer Polytechnic Institute, Troy, New York (1984).
[20] and , 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] and , The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Inform. Comput. 197 (2005) 1-21. | MR | Zbl
[22] , Restarting automata and their relations to the Chomsky hierarchy, in Proc. DLT 2003. Lect. Notes Comput. Sci. 2710 (2003) 55-74. | MR | Zbl
[23] , 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] , Two-way restarting automata and j-monotonicity, in Proc. SOFSEM 2001. Lect. Notes Comput. Sci. 2234 (2001) 316-325. | Zbl
[25] , A YACC extension for LRR grammar parsing. Theoret. Comput. Sci. 52 (1987) 91-143. | MR | Zbl
[26] and , Noncanonical extensions of bottom-up parsing techniques. SIAM J. Comput. 5 (1976) 231-250. | MR | Zbl
Cité par Sources :
