Charles Explorer logo
🇨🇿

Cut Hierarchies for Restarting automata and Marcus t-Contextual grammars

Publikace na Matematicko-fyzikální fakulta |
2005

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

The t-contextual grammars are generalizations of Marcus contextual grammars, which insert t contexts in each derivation step. Here the generative capacity of these grammars is studied for the case of a regular selection mapping.

If this selection mapping satisfies the additional requirement that in each derivation step all~t insertions are performed in the same neighbourhood, then the languages generated by these grammars can be recognized by restarting automata with cut index t. These are restarting automata for which each rewrite step consists in the deletion of up to t subwords from the content of the read/write window.

The classes of languages that are accepted by certain variants of restarting automata with limited cut-index are studied.