Languages polylog-time reducible to dot-depth 1/2 (Q859980): Difference between revisions

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 \(\mathcal C\) and \(\mathcal D\) source: (a) Either \(\mathcal C\) is contained in NP, or \(\mathcal C\) contains coUP. (b) Either \(\mathcal D\) is contained in P, or \(\mathcal 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 \(L_n\) such that \(L_n\)'s balanced leaf-language class is 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.