RAIRO-Theor. Inf. Appl.
Volume 39, Number 3, July-September 2005Foundations of Software Science and Computer Structures (FOSSECAS'04)
|Page(s)||455 - 509|
|Published online||15 July 2005|
Distance desert automata and the star height problem
Dresden University of Technology, Institute of Algebra, 01062 Dresden, Germany; firstname.lastname@example.org
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 bound for the star height problem.
Mathematics Subject Classification: 20M35 / 68Q17 / 68Q70
Key words: Recognizable languages / star height / distance automata.
© EDP Sciences, 2005
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.