Restarting Automata and Variants of j-Monotonicity.
Martin Plátek, Friedrich Otto, František Mráz · 2003
In the literature various notions of (non-) monotonicity of restarting automata have been studied. Here we introduce two new variants of (non-) monotonicity for restarting automata and for two-way restarting automata: left (non-) monotonicity and right-left (non-) monotonicity. It is shown that for the various types of deterministic and nondeterministic (two-way) restarting automata without auxiliary symbols, these notions yield infinite hierarchies. In addition, we compare the various hierarchies to each other. 1