Aufsatz in einer Fachzeitschrift
Deterministic two-way restarting automata and Marcus contextual grammars



Details zur Publikation
Autor(inn)en:
Jurdzinski, T.; Otto, F.; Mraz, F.; Platek, M.
Verlag:
Polish Mathematical Society
Publikationsjahr:
2005
Zeitschrift:
Fundamenta Informaticae
Seitenbereich:
217-228
Jahrgang/Band:
64
Erste Seite:
217
Letzte Seite:
228
ISSN:
0169-2968

Zusammenfassung, Abstract
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.


Autor(inn)en / Herausgeber(innen)

Zuletzt aktualisiert 2019-25-07 um 10:35