Voir la notice de l'article provenant de la source Numdam
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.
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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
Cité par Sources :