Displaying 161 – 180 of 220

Showing per page

Distance desert automata and the star height problem

Daniel Kirsten (2005)

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

We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 2 2 𝒪 ( n ) space whether the language accepted by an n -state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity bound...

Distance desert automata and the star height problem

Daniel Kirsten (2010)

RAIRO - Theoretical Informatics and Applications

We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity...

Currently displaying 161 – 180 of 220