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

Friedrich Otto

RAIRO - Theoretical Informatics and Applications (2009)

  • Volume: 43, Issue: 3, page 653-665
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Otto, 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
  1. T.P. Baker, Extending lookahead for LR parsers. J. Comput. System. Sci. 22 (1981) 243–259.  Zbl0472.68049
  2. M. Bermudez and K. Schimpf, Practical arbitrary lookahead LR parsing. J. Comput. System. Sci. 41 (1990) 230–250.  Zbl0698.68070
  3. G. Buntrock and F. Otto, Growing context-sensitive languages and Church-Rosser languages. Inform. Comput. 141 (1998) 1–36.  Zbl0894.68093
  4. K. Čulik II and R. Cohen, LR-regular grammars - an extension of LR(k) grammars. J. Comput. System. Sci.7 (1973) 66–96.  Zbl0253.68014
  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.  Zbl0977.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.  Zbl0507.68044
  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.  Zbl0942.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.  Zbl1056.68095
  10. T. Jurdziński and F. Otto, Shrinking restarting automata. Int. J. Found. Comput. Sci. 18 (2007) 361–385.  Zbl1112.68087
  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.  Zbl1132.68450
  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.  Zbl1142.68423
  13. M. Kutrib and A. Malcher, When Church-Rosser becomes context-free. Int. J. Found. Comput. Sci. 18 (2007) 1293–1302.  Zbl1183.68344
  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.  Zbl0652.68093
  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.  Zbl1185.68394
  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).  
  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.  Zbl1075.68046
  22. F. Otto, Restarting automata and their relations to the Chomsky hierarchy, in Proc. DLT 2003. Lect. Notes Comput. Sci.2710 (2003) 55–74.  Zbl1037.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.  Zbl1052.68628
  25. B. Seité, A YACC extension for LRR grammar parsing. Theoret. Comput. Sci. 52 (1987) 91–143.  Zbl0627.68070
  26. T. Szymanski and J. Williams, Noncanonical extensions of bottom-up parsing techniques. SIAM J. Comput. 5 (1976) 231–250.  Zbl0373.68048

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.