Issue Theoret. Informatics Appl. Volume 39, Number 2, April-June 2005 Page(s) 325 - 342 DOI 10.1051/ita:2005021

Theoret. Informatics Appl. 39, 325-342 (2005)
DOI: 10.1051/ita:2005021

Hierarchies of weakly monotone restarting automata

Frantisek Mráz¹ and Friedrich Otto<sup>2

1</sup>  Department of Computer Science, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic; mraz@ksvi.ms.mff.cuni.cz
²  Fachbereich Mathematik/Informatik, Universität Kassel, 34109 Kassel, Germany; otto@theory.informatik.uni-kassel.de

(Received June 11, 2003. Accepted May 5, 2004.)

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.

Mathematics Subject Classification. 68Q10, 68Q42, 68Q45

Key words: Restarting automata -- weak monotonicity -- hierarchies


© EDP Sciences 2005

What is OpenURL?