Abstract: Given a family of recognizable languages and
recognizable languages the
relative inclusion star height problem means to compute the minimal star height
of some rational expression r over satisfying
We show that this
problem is of elementary complexity and give a detailed analysis of its
complexity depending on the representation of and and whether
are
singletons. We also consider the case
Keywords and phrases: recognizable sets, star height, distance desert automata.
