Publication at Faculty of Mathematics and Physics |
2005
Abstract
The t-contextual grammars are generalizations of Marcus contextual grammars, which insert t contexts in each derivation step. When restricted to regular selection mappings, these grammars correspond to t-FRR-automata with cut-index one.
These are FRR-automata that are allowed to perform up to t deletion operations in each cycle that each delete a single factor only. Here the expressive power of these automata is studied for the special case that they satisfy certain monotonicity conditions.