Abstract
Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method can be modelled by restarting automata.
Here we study a new type of restarting automaton, the so-called t-sRL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size 1 only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle.
We study the correctness preservation of these automata on the one hand, and the complexity of these automata on the other hand, establishing a complexity measure that is based on the description of t-sRL-automata in terms of so-called meta-instructions. We present a hierarchy result and we show that the correctness preserving nondeterministic t-sRL-automata are not stronger than the deterministic t-sRL-automata.