Journal article
Hierarchies of weakly monotone restarting automata



Publication Details
Authors:
Mraz, F.; Otto, F.
Publication year:
2005
Journal:
RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Pages range:
325-342
Volume number:
39
ISSN:
0988-3754

Abstract
It is known that the weakly monotone restarting automata accept exactly the growing context-sensitive languages. We introduce a measure on the degree of weak monotonicity and show that the language classes obtained in this way form strict hierarchies for the various types of deterministic and nondeterministic restarting automata without auxiliary symbols.


Authors/Editors

Last updated on 2019-25-07 at 11:15