Hierarchies of weakly monotone restarting automata

František Mráz; Friedrich Otto

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

  • Volume: 39, Issue: 2, page 325-342
  • ISSN: 0988-3754

Abstract

top
It is known that the weakly monotone restarting automata accept exactly the growing context-sensitive languages. We introduce a measure on the degree of weak monotonicity and show that the language classes obtained in this way form strict hierarchies for the various types of deterministic and nondeterministic restarting automata without auxiliary symbols.

How to cite

top

Mráz, František, and Otto, Friedrich. "Hierarchies of weakly monotone restarting automata." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 39.2 (2005): 325-342. <http://eudml.org/doc/245968>.

@article{Mráz2005,
abstract = {It is known that the weakly monotone restarting automata accept exactly the growing context-sensitive languages. We introduce a measure on the degree of weak monotonicity and show that the language classes obtained in this way form strict hierarchies for the various types of deterministic and nondeterministic restarting automata without auxiliary symbols.},
author = {Mráz, František, Otto, Friedrich},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {restarting automata; weak monotonicity; hierarchies; Restarting automata},
language = {eng},
number = {2},
pages = {325-342},
publisher = {EDP-Sciences},
title = {Hierarchies of weakly monotone restarting automata},
url = {http://eudml.org/doc/245968},
volume = {39},
year = {2005},
}

TY - JOUR
AU - Mráz, František
AU - Otto, Friedrich
TI - Hierarchies of weakly monotone restarting automata
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2005
PB - EDP-Sciences
VL - 39
IS - 2
SP - 325
EP - 342
AB - It is known that the weakly monotone restarting automata accept exactly the growing context-sensitive languages. We introduce a measure on the degree of weak monotonicity and show that the language classes obtained in this way form strict hierarchies for the various types of deterministic and nondeterministic restarting automata without auxiliary symbols.
LA - eng
KW - restarting automata; weak monotonicity; hierarchies; Restarting automata
UR - http://eudml.org/doc/245968
ER -

References

top
  1. [1] E. Dahlhaus and M.K. Warmuth, Membership for growing context-sensitive grammars is polynomial. J. Comput. Syst. Sci. 33 (1986) 456–472. Zbl0625.68055
  2. [2] P. Jančar, F. Mráz, M. Plátek and J. Vogel, Restarting automata, in Proc. FCT’95, edited by H. Reichel. Springer, Berlin, Lect. Notes Comput. Sci. 965 (1995) 283–292. 
  3. [3] 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
  4. [4] T. Jurdziński, K. Loryś, G. Niemann and F. Otto, Some results on RWW- and RRWW-automata and their relationship to the class of growing context-sensitive languages. Tech. Report 14/01, Fachbereich Mathematik/Informatik, Universität Kassel (2001). Also: To appear in revised form in the J. Autom. Lang. Comb. Zbl1083.68057MR2198707
  5. [5] R. McNaughton, P. Narendran and F. Otto, Church-Rosser Thue systems and formal languages. J. Assoc. Comput. Mach. 35 (1988) 324–344. Zbl0652.68093
  6. [6] P. Narendran, Church-Rosser and related Thue systems. Ph.D. Thesis, Rensselaer Polytechnic Institute, Troy, New York (1984). 
  7. [7] G. Niemann and F. Otto, The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages, in Proc. FoSSaCS’98, edited by M. Nivat. Springer, Berlin, Lect. Notes Comput. Sci. 1378 (1998) 243–257. Zbl0908.68089
  8. [8] G. Niemann and F. Otto, On the power of RRWW-automata, in Words, Semigroups, and Transductions, edited by M. Ito, G. Păun and S. Yu. World Scientific, Singapore (2001) 341–355. 
  9. [9] G. Niemann and F. Otto, Further results on restarting automata, in Words, Languages and Combinatorics III, Proc., edited by M. Ito and T. Imaoka. World Scientific, Singapore (2003) 352–369. 
  10. [10] M. Straňáková, Selected types of pg-ambiguity. The Prague Bulletin of Mathematical Linguistics 72 (1999) 29–57. 
  11. [11] M. Straňáková, Selected types of pg-ambiguity: Processing based on analysis by reduction, in Text, Speech and Dialogue, 3rd Int. Workshop, Proc., edited by P. Sojka, I. Kopeček and K. Pala. Springer, Berlin, Lect. Notes Comput. Sci. 1902 (2000) 139–144. 

NotesEmbed ?

top

You must be logged in to post comments.