Charles Explorer logo
🇨🇿

Deterministic Two-Way Restarting Automata and Marcus Contextual Grammars

Publikace na Matematicko-fyzikální fakulta |
2005

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

It is known that for (right-) monotone deterministic one-way restarting automata, the use of auxiliary symbols does not increase the expressive power. Here we show that the same is true for deterministic two-way restarting automata that are right-left-monotone.

Moreover, we present a transformation of this kind of restarting automata into contextual grammars with regular selection.