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