Page 1

Displaying 1 – 3 of 3

Showing per page

Hierarchies of weakly monotone restarting automata

František Mráz, Friedrich Otto (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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.

Hierarchies of weakly monotone restarting automata

František Mráz, Friedrich Otto (2010)

RAIRO - Theoretical Informatics and Applications

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.

Currently displaying 1 – 3 of 3

Page 1