Marcus t-contextual grammars and cut hierarchies and monotonicity for restarting automata

The t-contextual grammars are generalizations of Marcus contextual grammars, which insert t contexts in each derivation step. If the selection mappings are regular and satisfy an additional locality restriction, then these grammars correspond in their expressive power to restarting automata with cut-index t. In the first part of the paper classes of languages are studied that are accepted by certain types of restarting automata with limited cut-index. As already R-automata with cut-index 1 accept NP-complete languages, additional restrictions in the form of certain monotonicity conditions are also considered. Without the locality restriction t-contextual grammars with regular selection correspond to t-RR-automata with cut-index one. These are RR-automata that are allowed to perform up to t deletion operations in each cycle that each delete a single factor only. In the second part of the paper the expressive power of these automata is studied, where the focus is on the special case that certain monotonicity conditions are satisfied. (c) 2006 Elsevier B.V. All rights reserved.