Degrees of Free Word-Order and Freely Rewriting Restarting Automata

Abstract

The degree of monotonicity can serve as a parameter (restriction) 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.