Parametrized Syntactic Analysis by Freely Rewriting Restarting Automata1

ABSTRACT The degree of monotonicity can serve as a parameter for the syntactic analysis by a generalized type of restarting automaton. Here we study the power of such constraints on computations of this restarting automaton. 1. Introduction The original motivation for introducing the restarting automaton was the desire to model the so-called analysis by reduction of natural languages (see, e.g., [3])