Publication at Faculty of Mathematics and Physics |
2019
Abstract
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 transformation of a deterministic monotone RWW-automaton of window size three into an equivalent automaton of the same type that has window size two. Further, we prove that for deterministic RWW-automata that are not monotone, window size two is not sufficient.