Monotonicity of Restarting Automata

Restarting automata constitute a special class of regulated length-reducing rewriting systems. In this paper, several versions of these automata and a (strict) monotonicity property imposed on their computations are considered. This yields three natural possibilities for defining when an automaton is (strictly) monotonic. A taxonomy of the relevant language classes is provided, and the decidability questions for the studied properties are answered.