As already 2-monotone R-automata accept NP-complete languages, we introduce a restricted variant of -monotonicity for restarting automata, called sequential -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 for any only accept context-free languages.
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 = {http://www.numdam.org/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 - http://www.numdam.org/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 http://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita:2007013/
[1] Transductions and Context-Free Languages. Teubner, Stuttgart (1979). | MR | Zbl
.[2] String-Rewriting Systems. Springer, New York (1993). | MR | Zbl
and ,[3] The language of final stack contents of a pushdown automaton is effectively regular. Mathematische Schriften Kassel 11/93, Universität Kassel (1993).
and ,[4] A note on pushdown store automata and regular systems. Proc. Amer. Math. Soc. 18 (1967) 263-268. | Zbl
,[5] Restarting automata, in FCT'95, Proc., edited by H. Reichel, Springer, Berlin. Lect. Notes Comput. Sci. 965 (1995) 283-292.
, , and .[6] On monotonic automata with a restart operation. J. Autom. Lang. Comb. 4 (1999) 287-311. | Zbl
, , and ,[7] Some results on RWW- and RRWW-automata and their relation to the class of growing context-sensitive languages. J. Autom. Lang. Comb. 9 (2004) 407-437. | Zbl
, , and ,[8] On the complexity of 2-monotone restarting automata, in DLT 2004, Proc., edited by C.S. Calude, E. Calude and M.J. Dinneen, Springer, Berlin. Lect. Notes Comput. Sci. 3340 (2004) 237-248. | Zbl
, , and ,[9] Degrees of non-monotonicity for restarting automata. Theoret. Comput. Sci. 369 (2006) 1-34. | Zbl
, , and ,[10] 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.
and ,[11] The computational complexity of rule-based part-of-speech tagging, in TSD 2003, Proc., edited by V. Matousek and P. Mautner, Springer, Berlin. Lect. Notes Comput. Sci. 2807 (2003) 82-89.
, and ,[12] Restarting automata and their relations to the Chomsky hierarchy, in Developments in Language Theory, Proc. DLT'2003, edited by Z. Esik and Z. Fülöp, Springer, Berlin. Lect. Notes Comput. Sci. 2710 (2003) 55-74. | Zbl
,[13] Restarting Automata, in Recent Advances in Formal Languages and Applications, Z. Ésik, C. Martin-Vide and V. Mitrana (Eds.), Springer, Berlin. Stud. Comput. Intelligence 25 (2006) 269-303. | Zbl
,[14] Two-way restarting automata and j-monotonicity, in Theory and Practice of Informatics, Proc. SOFSEM 2001, edited by L. Pacholski and P. Ružička, Springer-Verlag, Berlin. Lect. Notes Comput. Sci. 2234 (2001) 316-325. | Zbl
,[15] Degrees of (non)monotonicity of RRW-automata, in Preproceedings of the 3rd Workshop on Descriptional Complexity of Automata, Grammars and Related Structures, Report No. 16, edited by J. Dassow and D. Wotschke, Fakultät für Informatik, Universität Magdeburg (2001) 159-165.
and ,[16] Restarting automata: motivations and applications. In Workshop ‘Petrinetze' and 13. Theorietag ‘Formale Sprachen und Automaten', Proc., edited by M. Holzer, Institut für Informatik, Technische Universität München (2003) 90-96.
, and ,Cité par Sources :