Hierarchies of weakly monotone restarting automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 2, pp. 325-342.

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.

DOI : 10.1051/ita:2005021
Classification : 68Q10, 68Q42, 68Q45
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita:2005021/

[1] E. Dahlhaus and M.K. Warmuth, Membership for growing context-sensitive grammars is polynomial. J. Comput. Syst. Sci. 33 (1986) 456-472. | Zbl

[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] 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. | Zbl

[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. | MR | Zbl

[5] R. Mcnaughton, P. Narendran and F. Otto, Church-Rosser Thue systems and formal languages. J. Assoc. Comput. Mach. 35 (1988) 324-344. | Zbl

[6] P. Narendran, Church-Rosser and related Thue systems. Ph.D. Thesis, Rensselaer Polytechnic Institute, Troy, New York (1984).

[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. | Zbl

[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] 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] M. Straňáková, Selected types of pg-ambiguity. The Prague Bulletin of Mathematical Linguistics 72 (1999) 29-57.

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

Cité par Sources :