spacer
EDP Sciences Journals List
Home arrow Document
Subscriber Authentication Point
   
Issue Theoret. Informatics Appl.
Volume 39, Number 3, July-September 2005
Foundations of Software Science and Computer Structures (FOSSACS'04)
Page(s) 455 - 509
DOI 10.1051/ita:2005027

Theoret. Informatics Appl. 39, 455-509 (2005)
DOI: 10.1051/ita:2005027

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


Abstract
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^{{\cal 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.


Mathematics Subject Classification. 20M35, 68Q17, 68Q70.

Key words: Recognizable languages -- star height -- distance automata.


© EDP Sciences 2005


What is OpenURL?