Journal article
Deterministic two-way restarting automata and Marcus contextual grammars
Publication Details
Authors: | Jurdzinski, T.; Otto, F.; Mraz, F.; Platek, M. |
Publisher: | Polish Mathematical Society |
Publication year: | 2005 |
Journal: | Fundamenta Informaticae |
Pages range : | 217-228 |
Volume number: | 64 |
Start page: | 217 |
End page: | 228 |
ISSN: | 0169-2968 |
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.
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.
Projects
