Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T03:12:18.358Z Has data issue: false hasContentIssue false
  • English
  • Français

Left-to-right regular languages and two-way restarting automata

Published online by Cambridge University Press:  24 April 2009

Friedrich Otto
Friedrich Otto*
Affiliation:
Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany; [email protected]
Get access

Abstract

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.

Keywords

Left-to-right regular grammartwo-way restarting automatonmonotonicity.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 43 , Issue 3 , July 2009 , pp. 653 - 665
Copyright
© EDP Sciences, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Baker, T.P., Extending lookahead for LR parsers. J. Comput. System. Sci. 22 (1981) 243–259. CrossRef
Bermudez, M. and Schimpf, K., Practical arbitrary lookahead LR parsing. J. Comput. System. Sci. 41 (1990) 230–250. CrossRef
Buntrock, G. and Otto, F., Growing context-sensitive languages and Church-Rosser languages. Inform. Comput. 141 (1998) 1–36. CrossRef
Čulik II, K. and Cohen, R., LR-regular grammars - an extension of LR(k) grammars. J. Comput. System. Sci. 7 (1973) 66–96. CrossRef
Farré, J. and Fortes Gálvez, J., A bounded graph-connect construction for LR-regular parsers, in Proc. Compiler Construction, CC 2001. Lect. Notes Comput. Sci. 2027 (2001) 244–258. CrossRef
Heilbrunner, S., 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. CrossRef
Jančar, P., Mráz, F., Plátek, M. and Vogel, J., Restarting automata, in Proc. FCT 1995. Lect. Notes Comput. Sci. 965 (1995) 283–292. CrossRef
Jančar, P., Mráz, F., Plátek, M. and Vogel, J., On monotonic automata with a restart operation. J. Autom. Lang. Comb. 4 (1999) 287–311.
Jurdziński, T. and Loryś, K., Church-Rosser languages vs. UCFL, in Proc. ICALP 2002. Lect. Notes Comput. Sci. 2380 (2002) 147–158. CrossRef
Jurdziński, T. and Otto, F., Shrinking restarting automata. Int. J. Found. Comput. Sci. 18 (2007) 361–385. CrossRef
Jurdziński, T., Mráz, F., Otto, F. and Plátek, M., Monotone deterministic RL-automata don't need auxiliary symbols, in Proc. DLT 2005. Lect. Notes Comput. Sci. 3572 (2005) 284–295. CrossRef
Jurdziński, T., Mráz, F., Otto, F. and Plátek, M., Degrees of non-monotonicity for restarting automata. Theoret. Comput. Sci. 369 (2006) 1–34. CrossRef
Kutrib, M. and Malcher, A., When Church-Rosser becomes context-free. Int. J. Found. Comput. Sci. 18 (2007) 1293–1302. CrossRef
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.
McNaughton, R., Narendran, P. and Otto, F., Church-Rosser Thue systems and formal languages. J. ACM 35 (1988) 324–344. CrossRef
H. Messerschmidt, CD-Systems of Restarting Automata. Doctoral Dissertation, Fachbereich Elektrotechnik/Informatik, Universität Kassel (2008).
Messerschmidt, H. and Otto, F., On nonforgetting restarting automata that are deterministic and/or monotone, in Proc. CSR 2006. Lect. Notes Comput. Sci. 3967 (2006) 247–258. CrossRef
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.
P. Narendran, Church-Rosser and Related Thue Systems. Ph.D. thesis, Rensselaer Polytechnic Institute, Troy, New York (1984).
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.
Niemann, G. and Otto, F., The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Inform. Comput. 197 (2005) 1–21. CrossRef
Otto, F., Restarting automata and their relations to the Chomsky hierarchy, in Proc. DLT 2003. Lect. Notes Comput. Sci. 2710 (2003) 55–74. CrossRef
Otto, F., 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.
Plátek, M., Two-way restarting automata and j-monotonicity, in Proc. SOFSEM 2001. Lect. Notes Comput. Sci. 2234 (2001) 316–325. CrossRef
Seité, B., YACC, A extension for LRR grammar parsing. Theoret. Comput. Sci. 52 (1987) 91–143. CrossRef
Szymanski, T. and Williams, J., Noncanonical extensions of bottom-up parsing techniques. SIAM J. Comput. 5 (1976) 231–250. CrossRef