Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T12:31:35.054Z Has data issue: false hasContentIssue false

Distance desert automata and the star height problem

Published online by Cambridge University Press:  15 July 2005

Daniel Kirsten*
Affiliation:
Dresden University of Technology, Institute of Algebra, 01062 Dresden, Germany; kirsten@math.tu-dresden.de
Get access

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 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.

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable