Counting with Counterfree Automata

Christian Glasser, University at Wuerzburg, 2004


Abstract


We study the power of balanced and unbalanced 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 its 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 which can be done by
       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.