The notion of \emph{hyperdecidability} has been
introduced by the first author as a tool to prove
decidability of semidirect products of pseudovarieties
of semigroups. In this paper we consider some stronger
notions which lead to improved decidability results
allowing us in turn to establish the decidability of
some iterated semidirect products. Roughly speaking,
the decidability of a semidirect product follows
from a mild, commonly verified property of the first
factor plus the stronger property for all the other
factors. A key role in this study is played by
intermediate free semigroups (relatively free objects
of expanded type lying between relatively free and
relatively free profinite objects). As an application
of the main results, the decidability of the
Krohn--Rhodes (group) complexity is shown to follow
from non-algorithmic abstract properties likely to
be satisfied by the pseudovariety of all
finite aperiodic semigroups, thereby suggesting a
new approach to answer (affirmatively) the question
as to whether complexity is decidable.
1991 Mathematics Subject Classification:
primary 20M05, 20M07, 20M35; secondary 08B20.