Restarting Automata and Their Relations to the Chomsky Hierarchy

  • Friedrich Otto
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


The restarting automaton, introduced by Jančar et al in 1995, is motivated by the so-called ‘analysis by reduction,’ a technique from linguistics. By now there are many different models of restarting automata, and their investigation has proved very fruitful in that they offer an opportunity to study the influence of various kinds of resources on their expressive power. Here a survey on the various models and their properties is given, their relationships to the language classes of the Chomsky hierarchy are described, and some open problems are presented.


Expressive Power Regular Language Language Class Weakly Monotone Contextual Grammar 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Beaudry, M., Holzer, M., Niemann, G., Otto, F.: McNaughton families of languages. Theor. Comput. Sci. 290 (2003) 1581–1628zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Book, R.V.: Grammars with Time Functions. PhD dissertation. Harvard University, Cambridge, Massachusetts (1969)Google Scholar
  3. 3.
    Book, R.V., Otto, F.: String-Rewriting Systems. Springer, New York (1993)zbMATHGoogle Scholar
  4. 4.
    Buntrock, G.: Wachsende kontext-sensitive Sprachen. Habilitationsschrift, Fakult ät für Mathematik und Informatik, Universität Würzburg (1996)Google Scholar
  5. 5.
    Buntrock, G., Otto, F.: Growing context-sensitive languages and Church-Rosser languages. Infor. Comput. 141 (1998) 1–36zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Chytil, M.P., Plátek, M., Vogel, J.: A note on the Chomsky hierarchy. Bulletin of the EATCS 27 (1985) 23–30Google Scholar
  7. 7.
    Dahlhaus, E., Warmuth, M.: Membership for growing context-sensitive grammars is polynomial. J. Comput. Syst. Sci. 33 (1986) 456–472zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Ehrenfeucht, A., Păun, G., Rozenberg, G.: Contextual grammars and formal languages. In: Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Vol. 2. Springer, Berlin Heidelberg New York (1997) 237–293Google Scholar
  9. 9.
    Ehrenfeucht, A., Păun, G., Rozenberg, G.: On representing recursively enumerable languages by internal contextual languages. Theor. Comput. Sci. 205 (1998) 61–83zbMATHCrossRefGoogle Scholar
  10. 10.
    Gladkij, A.W.: On the complexity of derivations for context-sensitive grammars. Algebra i Logika 3 (1964) 29–44 (In Russian)zbMATHGoogle Scholar
  11. 11.
    Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, M.A. (1979)zbMATHGoogle Scholar
  12. 12.
    Jančar, P., Mráz, F., Plátek, M.: A taxonomy of forgetting automata. In: Borzyszkowski, A.M., Sokolowski, St. (eds.): MFCS’93, Proc., LNCS 711, Springer, Berlin (1993) 527–536Google Scholar
  13. 13.
    Jančar, P., Mráz, F., Plátek, M.: Forgetting automata and context-free languages. Acta Infor. 33 (1996) 409–420CrossRefGoogle Scholar
  14. 14.
    Jančar, P., Mráz, F., Plátek, M., Procházka, M., Vogel, J.: Restarting automata, Marcus grammars and context-free languages. In: Dassow, J. Rozenberg, G. and Salomaa, A. (eds.): DLT II, Proc., World Scientific, Singapore (1996) 102–111Google Scholar
  15. 15.
    Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting automata. In: Reichel, H. (ed.): FCT’95, Proc., LNCS 965, Springer, Berlin (1995) 283–292Google Scholar
  16. 16.
    Jančar, P., Mráz, F., Plátek, M., Vogel, J.: On restarting automata with rewriting. In: Păun, G., Salomaa, A. (eds.): New Trends in Formal Languages, LNCS 1218, Springer, Berlin (1997) 119–136Google Scholar
  17. 17.
    Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Monotonic rewriting automata with a restart operation. In: Plášil, F., Jeffery, K.G. (eds.): SOFSEM’97, Proc., LNCS 1338, Springer, Berlin (1997) 505–512Google Scholar
  18. 18.
    Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Different types of monotonicity for restarting automata. In: Arvind, V., Ramanujam, R. (eds.): FSTTCS’98, Proc., LNCS 1530, Springer, Berlin (1998) 343–354Google Scholar
  19. 19.
    Jančar, P., Mráz, F., Plátek, M., Vogel, J.: On monotonic automata with a restart operation. J. Autom. Lang. and Comb. 4 (1999) 287–311zbMATHMathSciNetGoogle Scholar
  20. 20.
    Jurdziński, T., Loryś, K.: Church-Rosser languages vs. UCFL. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.): ICALP’02, Proc., LNCS 2380, Springer, Berlin (2002) 147–158Google Scholar
  21. 21.
    Jurdziński, T., Loryś, K., Niemann, G., Otto, F.: Some results on RRW-and RRWW-automata and their relationship to the class of growing context-sensitive languages. Mathematische Schriften Kassel, no. 14/01, Fachbereich Mathematik/ Informatik, Universität Kassel (2001)Google Scholar
  22. 22.
    Marcus, S.: Contextual grammars and natural languages. In: Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Vol. 2. Springer, Berlin Heidelberg New York (1997) 215–235Google Scholar
  23. 23.
    McNaughton, R.: An insertion into the Chomsky hierarchy? In: Karhumäki, J., Maurer, H., Păun, G., Rozenberg, G. (eds.): Jewels are Forever. Springer, Berlin Heidelberg New York (1999) 204–212Google Scholar
  24. 24.
    McNaughton, R., Narendran, P., Otto, F.: Church-Rosser Thue systems and formal languages. J. Assoc. Comput. Mach. 35 (1988) 324–344zbMATHMathSciNetGoogle Scholar
  25. 25.
    Mráz, F.: Forgetting and Restarting Automata. PhD thesis, Charles University, Prague (2001)Google Scholar
  26. 26.
    Mráz, F.: Lookahead hierarchies of restarting automata. J. Autom. Lang. and Comb. 6 (2001) 493–506zbMATHMathSciNetGoogle Scholar
  27. 27.
    Mráz, F., Otto, F.: Hierarchies of weakly monotone restarting automata. In preparation.Google Scholar
  28. 28.
    Mráz, F., Plátek, M., Procházka, M.: Restarting automata, deleting, and Marcus grammars. In: Martín-Vide, C., Păun, G. (eds.): Recent Topics in Mathem. and Comput. Linguistics. Editura Academiei Române, Bukarest (2000) 218–233Google Scholar
  29. 29.
    Narendran, P.: Church-Rosser and related Thue systems. PhD thesis, Rensselaer Polytechnic Institute, Troy, New York (1984)Google Scholar
  30. 30.
    Niemann, G.: Regular Languages and Church-Rosser congruential languages. In: Freund, R., Kelemenová, A. (eds.): Grammar Systems 2000, Proc., Silesian University, Opava (2000) 359–370Google Scholar
  31. 31.
    Niemann, G.: Church-Rosser languages and related classes. Dissertation, Universit ät Kassel (2002)Google Scholar
  32. 32.
    Niemann, G., Otto, F.: The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. In: Nivat, M. (ed.): FoSSaCS’98, Proc., LNCS 1378, Springer, Berlin (1998) 243–257Google Scholar
  33. 33.
    Niemann, G., Otto, F.: Confluent internal contextual languages. In: Martin-Vide, C., Păun, G. (eds.): Recent Topics in Mathematical and Computational Linguistics. The Publishing House of the Romanian Academy, Bucharest (2000) 234–244Google Scholar
  34. 34.
    Niemann, G., Otto, F.: Restarting automata, Church-Rosser languages, and representations of r.e. languages. In: Rozenberg, G., Thomas, W. (eds.): DLT’99, Proc., World Scientific, Singapore (2000) 103–114Google Scholar
  35. 35.
    Niemann, G., Otto, F.: On the power of RRWW-automata. In: Ito, M., Păun, G., Yu, S. (eds.): Words, Semigroups, and Transductions. World Scientific, Singapore (2001) 341–355Google Scholar
  36. 36.
    Niemann, G., Otto, F.: Further results on restarting automata. In: Ito, M., Imaoka, T. (eds.): Words, Languages and Combinatorics III, Proc., World Scientific, Singapore (2003), to appearGoogle Scholar
  37. 37.
    Niemann, G., Waldmann, J.: Some regular languages that are Church-Rosser congruential. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.): DLT’01, Proc., LNCS 2295, Springer, Berlin (2002) 330–339Google Scholar
  38. 38.
    Niemann, G., Woinowski, J.R.: The growing context-sensitive languages are the acyclic context-sensitive languages. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.): DLT’01, Proc., LNCS 2295, Springer, Berlin (2002) 197–205Google Scholar
  39. 39.
    Otto, F., Katsura, M., Kobayashi, Y.: Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids. J. Symbol. Comput. 26 (1998) 621–648zbMATHCrossRefMathSciNetGoogle Scholar
  40. 40.
    Parikh, R.J.: On context-free languages. J. Assoc. Comput. Mach. 13 (1966) 570–581zbMATHMathSciNetGoogle Scholar
  41. 41.
    Plátek, M.: Two-way restarting automata and j-monotonicity. In: Pacholski, L., Ružička, P. (eds.): SOFSEM’01, Proc., LNCS 2234, Springer, Berlin (2001) 316–325Google Scholar
  42. 42.
    Plátek, M., Mráz, F.: Degrees of (non)monotonicity of RWW-automata. In: Dassow, J., Wotschke, D. (eds.): Preproceedings of the 3rd Workshop on Descriptional Complexity of Automata, Grammars and Related Structures. Report No. 16, Fakultät für Informatik, Universität Magdeburg (2001) 159–165Google Scholar
  43. 43.
    Rovan, B.: A framework for studying grammars. In: Gruska, I., Chytil, M. (eds.): MFCS’81, Proc., LNCS 118, Springer, Berlin (1981) 473–482Google Scholar
  44. 44.
    Solms, S.H. von: The characterization by automata of certain classes of languages in the context sensitive area. Infor. Control 27 (1975) 262–271CrossRefzbMATHGoogle Scholar
  45. 45.
    Straňáková, M.: Selected types of pg-ambiguity. The Prague Bulletin of Mathematical Linguistics 72 (1999) 29–57Google Scholar
  46. 46.
    Straňáková, M.: Selected types of pg-ambiguity: Processing based on analysis by reduction. In: Sojka, P., Kopeček, I., Pala, K. (eds.): Text, Speech and Dialogue, 3rd Int. Workshop, TSD 2000, Proc., LNCS 1902, Springer, Berlin (2000) 139–144CrossRefGoogle Scholar
  47. 47.
    Woinowski, J.: A normal form for Church-Rosser language systems. In: Middeldorp, A. (ed.): RTA’01, Proc., LNCS 2051, Springer, Berlin (2001) 322–337Google Scholar
  48. 48.
    Woinowski, J.: Church-Rosser languages and their application to parsing problems. Dissertation, Technische Universität Darmstadt (2001)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Friedrich Otto
    • 1
  1. 1.Fachbereich Mathematik/InformatikUniversität KasselKasselGermany

Personalised recommendations