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.
Mots clés : restarting automata, weak monotonicity, hierarchies
@article{ITA_2005__39_2_325_0,
author = {Mr\'az, Franti\v{s}ek and Otto, Friedrich},
title = {Hierarchies of weakly monotone restarting automata},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {325--342},
publisher = {EDP-Sciences},
volume = {39},
number = {2},
year = {2005},
doi = {10.1051/ita:2005021},
mrnumber = {2142116},
zbl = {1101.68587},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2005021/}
}
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 SP - 325 EP - 342 VL - 39 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2005021/ DO - 10.1051/ita:2005021 LA - en ID - ITA_2005__39_2_325_0 ER -
%0 Journal Article %A Mráz, František %A Otto, Friedrich %T Hierarchies of weakly monotone restarting automata %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2005 %P 325-342 %V 39 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2005021/ %R 10.1051/ita:2005021 %G en %F ITA_2005__39_2_325_0
Mráz, František; Otto, Friedrich. Hierarchies of weakly monotone restarting automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 2, pp. 325-342. doi : 10.1051/ita:2005021. http://www.numdam.org/articles/10.1051/ita:2005021/
[1] and, Membership for growing context-sensitive grammars is polynomial. J. Comput. Syst. Sci. 33 (1986) 456-472. | Zbl
[2] ,, and, Restarting automata, in Proc. FCT'95, edited by H. Reichel. Springer, Berlin, Lect. Notes Comput. Sci. 965 (1995) 283-292.
[3] ,, and, On monotonic automata with a restart operation. J. Autom. Lang. Comb. 4 (1999) 287-311. | Zbl
[4] ,, and, 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. | MR | Zbl
[5] , and, Church-Rosser Thue systems and formal languages. J. Assoc. Comput. Mach. 35 (1988) 324-344. | Zbl
[6] , Church-Rosser and related Thue systems. Ph.D. Thesis, Rensselaer Polytechnic Institute, Troy, New York (1984).
[7] and, 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. | Zbl
[8] and, 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] and, 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] , Selected types of pg-ambiguity. The Prague Bulletin of Mathematical Linguistics 72 (1999) 29-57.
[11] , 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.
Cité par Sources :
