We introduce the notion of nested distance desert automata as a joint generalization and further development 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(n2) 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). We also show some decidability results for some substitution problems for recognizable languages.

Given a family of recognizable languages L1, . . . ,Lm and recognizable languages K1 ⊆ K2, the relative inclusion star height problem means to compute the minimal star height of some rational expression r over L1, . . . ,Lm satisfying K1 ⊆ L(r) ⊆ K2. We show that this problem is of elementary complexity and give a detailed analysis its complexity depending on the representation of K1 and K2 and whether L1, . . . ,Lm are singletons.