Languages polylog-time reducible to dot-depth 1/2

摘要

We study (i) regular languages that are polylog-time reducible to languages of 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. This implies that both classes are decidable. In addition, we show that a language is in class (ii) if and only if the language and its complement are in class (i). Our observations have three consequences.(1)Gap theorems for balanced regular-leaf-language definable classes C and D:(a)Either C is contained in NP, or C contains coUP.(b)Either D is contained in P, or D contains UP or coUP. We also 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 these reductions cannot count). We construct languages of arbitrary dot-depth that are reducible to languages of dot-depth 1/2.(3)Unbalanced star-free leaf languages can be much stronger than balanced ones. We construct star-free regular languages Ln such that Ln's balanced leaf-language class is NP, but the unbalanced leaf-language class of Ln contains level n of the unambiguous alternation hierarchy. This demonstrates the power of unbalanced computations.