Here we show that for monotone RWW- (and RRWW-) automata, window size two is sufficient, both in the nondeterministic as well as in the deterministic case. For the former case, this is done by proving that each context-free language is already accepted by a monotone RWW-automaton of window size two. In the deterministic case, we first prove that each deterministic pushdown automaton can be simulated by a deterministic monotone RWW-automaton of window size three, and then we present a construction that transforms a deterministic monotone RWW-automaton of window size three into an equivalent automaton of the same type that has window size two. Furthermore, we study the expressive power of shrinking RWW- and RRWW-automata the window size of which is just one or two. We show that for shrinking RRWW-automata that are nondeterministic, window size one suffices, while for nondeterministic shrinking RWW-automata, we already need window size two to accept all growing context-sensitive languages. In the deterministic case, shrinking RWW- and RRWW-automata of window size one accept only regular languages, while those of window size two characterize the Church-Rosser languages.
Keywords: Restarting automaton, window size, weight function, language class
@article{ITA_2021__55_1_A11_0,
author = {Mr\'az, Franti\v{s}ek and Otto, Friedrich},
editor = {Holzer, Markus and Sempere, Jos\'e M.},
title = {On {Restarting} {Automata} {With} {Auxiliary} {Symbols} and {Small} {Window} {Size}},
journal = {RAIRO. Theoretical Informatics and Applications},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ita/2021003},
mrnumber = {4289537},
zbl = {1508.68200},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ita/2021003/}
}
TY - JOUR AU - Mráz, František AU - Otto, Friedrich ED - Holzer, Markus ED - Sempere, José M. TI - On Restarting Automata With Auxiliary Symbols and Small Window Size JO - RAIRO. Theoretical Informatics and Applications PY - 2021 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ita/2021003/ DO - 10.1051/ita/2021003 LA - en ID - ITA_2021__55_1_A11_0 ER -
%0 Journal Article %A Mráz, František %A Otto, Friedrich %E Holzer, Markus %E Sempere, José M. %T On Restarting Automata With Auxiliary Symbols and Small Window Size %J RAIRO. Theoretical Informatics and Applications %D 2021 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ita/2021003/ %R 10.1051/ita/2021003 %G en %F ITA_2021__55_1_A11_0
Mráz, František; Otto, Friedrich. On Restarting Automata With Auxiliary Symbols and Small Window Size. RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 9. doi: 10.1051/ita/2021003
[1] , and , Context-free languages and pushdown automata, in Handbook of Formal Languages, Vol. 1, Word, Language, Grammar, edited by and . Springer, Berlin (1997) 111–174. | MR | DOI
[2] and , Growing context-sensitive languages and Church-Rosser languages. Inf. Comput. 141 (1998) 1–36. | MR | Zbl | DOI
[3] and , Membership for growing context-sensitive grammars is polynomial. J. Comput. Syst. Sci. 33 (1986) 456–472. | MR | Zbl | DOI
[4] and , An approach to a unified theory of automata. Bell Syst. Tech. J. 46 (1967) 1793–1829. | MR | Zbl | DOI
[5] and , Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979). | MR | Zbl
[6] , , and , Restarting automata, in FCT’95, Proc., edited by . Lecture Notes in Computer Science 965. Springer, Berlin (1995) 283–292. | MR | Zbl | DOI
[7] , , and , On monotonic automata with a restart operation. J. Autom. Lang. Combin. 4 (1999) 287–311. | MR | Zbl
[8] , , and , Some results on RWW- and RRWW-automata and their relation to the class of growing context-sensitive languages. J. Autom. Lang. Combin. 9 (2004) 407–437. | MR | Zbl
[9] , , and , Degrees of non-monotonicity for restarting automata. Theor. Computer Sci. 369 (2006) 1–34. | MR | Zbl | DOI
[10] and , Shrinking restarting automata. Int. J. Found. Comput. Sci. 18 (2007) 361–385. | MR | Zbl | DOI
[11] , , and , On left-monotone deterministic restarting automata, in DLT 2004, Proc., edited by , and . Lecture Notes in Computer Science 3340. Springer, Berlin (2004) 249–260. | MR | Zbl
[12] and , On the descriptional complexity of the window size for deleting restarting automata. Int. J. Found. Comput. Sci. 24 (2013) 831–846. | MR | Zbl | DOI
[13] and , Succinct description of regular languages by weak restarting automata. Inf. Comput. 206 (2008) 1152–1160. | MR | Zbl | DOI
[14] and , On ordered RRWW-automata, in DLT 2016, Proc., edited by and . Lecture Notes in Computer Science 9840. Springer, Heidelberg (2016) 268–279. | MR | Zbl
[15] and , On the effects of nondeterminism on ordered restarting automata, in SOFSEM 2016, Proc., edited by , and . Lecture Notes in Computer Science 9587. Springer, Heidelberg (2016) 369–380. | MR | Zbl
[16] and , Nondeterministic ordered restarting automata. Int. J. Found. Comput. Sci. 29 (2018) 663–685. | MR | Zbl | DOI
[17] , and , Church-Rosser Thue systems and formal languages. J. Assoc. Comput. Mach. 35 (1988) 324–344. | MR | Zbl | DOI
[18] , Lookahead hierarchies of restarting automata. J. Autom. Lang. Combin. 6 (2001) 493–506. | MR | Zbl
[19] and , Ordered restarting automata for picture languages, in SOFSEM 2014, Proc., edited by , , , and . Lecture Notes in Computer Science 8327. Springer, Heidelberg (2014) 431–442. | MR | Zbl
[20] and Window size two suffices for deterministic monotone RWW-automata, in Eleventh Workshop on Non-Classical Models of Automata and Applications (NCMA 2019), Proc., edited by , , and . volume 336 of books@ocg.at. Österreichische Computer Gesellschaft, Wien, (2019) 139–154.
[21] and On shrinking restarting automata of window size one and two, in DLT 2019, Proc., edited by and . Lecture Notes in Computer Science 11647. Springer, Heidelberg (2019) 140–153. | Zbl | MR
[22] , On a hierarchy of sensing Watson-Crick finite automata languages. J. Logic Comput. 23 (2013) 855–872. | MR | Zbl | DOI
[23] and , Restarting automata, Church-Rosser languages, and confluent internal contextual languages. Mathematische Schriften Kassel 4/99, Universität Kassel (1999).
[24] and , Restarting automata, Church-Rosser languages, and representations of r.e. languages, in Developments in Language Theory – Foundations, Applications, and Perspectives, DLT 1999, Proc., edited by and . World Scientific, Singapore (2000) 103–114. | MR | Zbl
[25] and , The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Inf. Comput. 197 (2005) 1–21. | MR | Zbl | DOI
[26] and , On left-monotone restarting automata. Mathematische Schriften Kassel 17/03, Universität Kassel (2003).
[27] , On lookahead hierarchies for monotone and deterministic restarting automata with auxiliary symbols (Extended abstract), in DLT 2010, Proc., edited by , and . Lecture Notes in Computer Science 6224. Springer, Berlin (2010) 440–441. | Zbl | DOI
[28] , Restarting automata with auxiliary symbols and small lookahead, in LATA 2011, Proc., edited by , and . Lecture Notes in Computer Science 6638. Springer, Berlin (2011) 499–510. | Zbl | DOI
[29] , Restarting automata with auxiliary symbols restricted by lookahead size. Int. J. Computer Math. 92 (2015) 908–938. | MR | Zbl | DOI
[30] and , Finite-change automata, in 4th GI Conference, Proc., edited by . Lecture Notes in Computer Science 67. Springer, Berlin (1979) 91–100. | MR | Zbl | DOI
Cité par Sources :
Some of the results of this paper have been announced at NCMA 2019 in Valencia, Spain, July 2019, and at DLT 2019 in Warsaw, Poland, August 2019. Extended abstracts can be found in the proceedings of these conferences [20, 21].
