We study the power of balanced regular leaf-languages.
First, we investigate (i) regular languages that are
polylog-time reducible to languages in dot-depth 1/2 and
(ii) regular languages that are polylog-time decidable.
For both classes we provide

- forbidden-pattern characterizations, and
- characterizations in terms of regular expressions.

Both ... more >>>

We introduce the polynomial-time tree reducibility
(ptt-reducibility). Our main result states that for
languages $B$ and $C$ it holds that
$B$ ptt-reduces to $C$ if and only if
the unbalanced leaf-language class of $B$ is robustly contained in
the unbalanced leaf-language class of $C$.
... more >>>

The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results:

1. The classes of ... more >>>