Left-to-right regular languages and two-way restarting automata
RAIRO - Theoretical Informatics and Applications (2009)
- Volume: 43, Issue: 3, page 653-665
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topOtto, Friedrich. "Left-to-right regular languages and two-way restarting automata." RAIRO - Theoretical Informatics and Applications 43.3 (2009): 653-665. <http://eudml.org/doc/250584>.
@article{Otto2009,
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.
},
author = {Otto, Friedrich},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Left-to-right regular grammar; two-way restarting automaton; monotonicity.; left-to-right regular grammar; monotonicity},
language = {eng},
month = {4},
number = {3},
pages = {653-665},
publisher = {EDP Sciences},
title = {Left-to-right regular languages and two-way restarting automata},
url = {http://eudml.org/doc/250584},
volume = {43},
year = {2009},
}
TY - JOUR
AU - Otto, Friedrich
TI - Left-to-right regular languages and two-way restarting automata
JO - RAIRO - Theoretical Informatics and Applications
DA - 2009/4//
PB - EDP Sciences
VL - 43
IS - 3
SP - 653
EP - 665
AB -
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.
LA - eng
KW - Left-to-right regular grammar; two-way restarting automaton; monotonicity.; left-to-right regular grammar; monotonicity
UR - http://eudml.org/doc/250584
ER -
References
top- T.P. Baker, Extending lookahead for LR parsers. J. Comput. System. Sci. 22 (1981) 243–259.
- M. Bermudez and K. Schimpf, Practical arbitrary lookahead LR parsing. J. Comput. System. Sci. 41 (1990) 230–250.
- G. Buntrock and F. Otto, Growing context-sensitive languages and Church-Rosser languages. Inform. Comput. 141 (1998) 1–36.
- K. Čulik II and R. Cohen, LR-regular grammars - an extension of LR(k) grammars. J. Comput. System. Sci.7 (1973) 66–96.
- 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.
- 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.
- 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.
- 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.
- T. Jurdziński and K. Loryś, Church-Rosser languages vs. UCFL, in Proc. ICALP 2002. Lect. Notes Comput. Sci.2380 (2002) 147–158.
- T. Jurdziński and F. Otto, Shrinking restarting automata. Int. J. Found. Comput. Sci. 18 (2007) 361–385.
- 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.
- 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.
- M. Kutrib and A. Malcher, When Church-Rosser becomes context-free. Int. J. Found. Comput. Sci. 18 (2007) 1293–1302.
- 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.
- R. McNaughton, P. Narendran and F. Otto, Church-Rosser Thue systems and formal languages. J. ACM 35 (1988) 324–344.
- H. Messerschmidt, CD-Systems of Restarting Automata. Doctoral Dissertation, Fachbereich Elektrotechnik/Informatik, Universität Kassel (2008).
- 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.
- 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.
- 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.
- F. Otto, Restarting automata and their relations to the Chomsky hierarchy, in Proc. DLT 2003. Lect. Notes Comput. Sci.2710 (2003) 55–74.
- 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.
- M. Plátek, Two-way restarting automata and j-monotonicity, in Proc. SOFSEM 2001. Lect. Notes Comput. Sci.2234 (2001) 316–325.
- B. Seité, A YACC extension for LRR grammar parsing. Theoret. Comput. Sci. 52 (1987) 91–143.
- T. Szymanski and J. Williams, Noncanonical extensions of bottom-up parsing techniques. SIAM J. Comput. 5 (1976) 231–250.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.