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 classes are decidable. The intersection of class (i)
with their complement is exactly class (ii).

We apply our observations and obtain three consequences.

1. Gap theorems for balanced regular-leaf-language
definable classes C and D:
- Either C is contained in NP,
or C contains coUP.
- Either D is contained in P,
or D contains UP or coUP.
Also we extend both theorems such that no promise
classes are involved. Formerly, such gap theorems
were known only for the unbalanced approach.

2. Polylog-time reductions can tremendously decrease
dot-depth complexity (despite that they cannot count).
We exploit a weak type of counting possible with
counterfree automata, and construct languages of
arbitrary dot-depth that are reducible to languages
in dot-depth 1/2.

3. Unbalanced starfree leaf-languages can be much stronger
than balanced ones. We construct starfree regular
languages L(n) such that the balanced leaf-language class
of L(n) is contained in NP, but the unbalanced
leaf-language class of L(n) contains level n of the
unambiguous alternation hierarchy. This demonstrates
the power of unbalanced computations.