×

Left-to-right regular languages and two-way restarting automata. (English) Zbl 1176.68107

Summary: 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.

MSC:

68Q45 Formal languages and automata

Software:

UCFL
PDFBibTeX XMLCite
Full Text: DOI EuDML Link

References:

[1] T.P. Baker, Extending lookahead for LR parsers. J. Comput. System. Sci. 22 (1981) 243-259. · Zbl 0472.68049 · doi:10.1016/0022-0000(81)90030-1
[2] M. Bermudez and K. Schimpf, Practical arbitrary lookahead LR parsing. J. Comput. System. Sci. 41 (1990) 230-250. Zbl0698.68070 · Zbl 0698.68070 · doi:10.1016/0022-0000(90)90037-L
[3] G. Buntrock and F. Otto, Growing context-sensitive languages and Church-Rosser languages. Inform. Comput. 141 (1998) 1-36. · Zbl 0894.68093 · doi:10.1006/inco.1997.2681
[4] K. Čulik II and R. Cohen, LR-regular grammars - an extension of LR(k) grammars. J. Comput. System. Sci.7 (1973) 66-96. · Zbl 0253.68014 · doi:10.1016/S0022-0000(73)80050-9
[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. · Zbl 0507.68044 · doi:10.1016/0304-3975(88)90008-4
[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.
[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. · 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. · Zbl 1056.68095
[10] T. Jurdziński and F. Otto, Shrinking restarting automata. Int. J. Found. Comput. Sci. 18 (2007) 361-385. · Zbl 1112.68087 · doi:10.1142/S0129054107004723
[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. · Zbl 1132.68450 · doi:10.1007/b137735
[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 · doi:10.1016/j.tcs.2006.08.029
[13] M. Kutrib and A. Malcher, When Church-Rosser becomes context-free. Int. J. Found. Comput. Sci. 18 (2007) 1293-1302. · Zbl 1183.68344 · doi:10.1142/S0129054107005339
[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. · Zbl 0652.68093 · doi:10.1145/42282.42284
[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. · Zbl 1185.68394 · doi:10.1007/11753728_26
[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). · Zbl 0592.03025
[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.
[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. · Zbl 1075.68046 · doi:10.1016/j.ic.2004.09.003
[22] F. Otto, Restarting automata and their relations to the Chomsky hierarchy, in Proc. DLT 2003. Lect. Notes Comput. Sci.2710 (2003) 55-74. · 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 Intelligence25 (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. · Zbl 0627.68070 · doi:10.1016/0304-3975(87)90082-X
[26] T. Szymanski and J. Williams, Noncanonical extensions of bottom-up parsing techniques. SIAM J. Comput. 5 (1976) 231-250. Zbl0373.68048 · Zbl 0373.68048 · doi:10.1137/0205019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.