Sequential monotonicity for restarting automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 2, pp. 157-175.

Voir la notice de l'article dans Numdam

As already 2-monotone R-automata accept NP-complete languages, we introduce a restricted variant of j-monotonicity for restarting automata, called sequential j-monotonicity. For restarting automata without auxiliary symbols, this restricted variant still yields infinite hierarchies. However, for restarting automata with auxiliary symbols, all degrees of sequential monotonicity collapse to the first level, implying that RLWW-automata that are sequentially monotone of degree j for any j≥1 only accept context-free languages.

DOI : 10.1051/ita:2007013
Classification : 68Q45
Mots-clés : restarting automaton, sequential monotonicity, hierarchies 
@article{ITA_2007__41_2_157_0,
     author = {Jurdzi\'nski, Tomasz and Otto, Friedrich},
     title = {Sequential monotonicity for restarting automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {157--175},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {2},
     year = {2007},
     doi = {10.1051/ita:2007013},
     mrnumber = {2350642},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2007013/}
}
TY  - JOUR
AU  - Jurdziński, Tomasz
AU  - Otto, Friedrich
TI  - Sequential monotonicity for restarting automata
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2007
SP  - 157
EP  - 175
VL  - 41
IS  - 2
PB  - EDP-Sciences
UR  - https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2007013/
DO  - 10.1051/ita:2007013
LA  - en
ID  - ITA_2007__41_2_157_0
ER  - 
%0 Journal Article
%A Jurdziński, Tomasz
%A Otto, Friedrich
%T Sequential monotonicity for restarting automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2007
%P 157-175
%V 41
%N 2
%I EDP-Sciences
%U https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2007013/
%R 10.1051/ita:2007013
%G en
%F ITA_2007__41_2_157_0
Jurdziński, Tomasz; Otto, Friedrich. Sequential monotonicity for restarting automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 2, pp. 157-175. doi : 10.1051/ita:2007013. https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2007013/

Cité par Sources :