  We consider algorithms and lower bounds for various problems over forest
languages; as input models we allow forest algebras, deterministic forest
automata and nondeterministic forest automata. For the equivalence problem, we
give an almost-linear-time algorithm for both forest algebras and deterministic
forest automata; this is complemented by a polynomial time hardness result. The
emptiness problem is complete for polynomial time over each of the three
models. Additionally, we consider the emptiness of intersection problem for
forest algebras and deterministic forest automata; this problem turns out to be
complete for exponential time. It is well-known that the corresponding problems
for word languages are complete for nondeterministic logarithmic space and for
polynomial space, respectively.
  Equipped with this toolbox of algorithms and lower bounds, we consider
various inclusion problems for regular forest languages under substitutions.
The substitutions in this paper replace leaf variables by forest languages.
Depending on the direction of the inclusion, the problem for a given
substitution is either complete for polynomial time or for exponential time; in
particular, the equivalence problem under substitutions is complete for
exponential time and, hence, more difficult than the equivalence problem for
forest languages without substitutions. If we ask whether there exists a
substitution such that a given inclusion holds, then this problem is either
complete for NP or exponential time, depending on whether we consider inclusion
or equivalence; moreover, the problem is undecidable if the substitution is
applied on both sides.
