RAIRO-Theor. Inf. Appl.
Volume 55, 2021
11th Workshop on Non-classical Models of Automata and Applications (NCMA 2019)
|Number of page(s)||31|
|Published online||22 July 2021|
On restarting automata with auxiliary symbols and small window size*
Charles University, Faculty of Mathematics and Physics,
Malostranské nám. 25,
Prague 1, Czech Republic.
2 Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany.
** Corresponding author: firstname.lastname@example.org
Accepted: 29 April 2021
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.
Mathematics Subject Classification: 68Q45 / 68Q42
Key words: Restarting automaton / window size / weight function / language class
© The authors. Published by EDP Sciences, 2021
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.