RAIRO - Theoretical Informatics and Applications

Research Article

Distance desert automata and the star height problem

Daniel Kirsten

Dresden University of Technology, Institute of Algebra, 01062 Dresden, Germany; kirsten@math.tu-dresden.de


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 22 O(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 for the star height problem.

(Online publication July 15 2005)

Key Words:

  • Recognizable languages;
  • star height;
  • distance automata.

Mathematics Subject Classification:

  • 20M35;
  • 68Q17;
  • 68Q70