The dot-depth hierarchy is a combinatorial parameterization of the starfree
regular languages, counting the alternating use of Boolean operations
versus concatenation. No algorithm is known to determine the dot-depth of a
given language, which is considered in the literature as one of the most
important open questions on regular languages.
We introduce a strict hierarchy L(n) of language classes which exhausts the
class of starfree regular languages. It is shown for all n>=0 that the classes
L(n) have decidable membership problems. As the main result, we prove that our
hierarchy is levelwise comparable by inclusion to the dot-depth hierarchy, more
precisely, L(n) contains all languages having dot-depth n + 1/2.
This yields a lower bound algorithm for the dot-depth of a given language.
The same results hold for a hierarchy L'(n) and the Straubing-Therien hierarchy.
On the technical side, we work with forbidden patterns in deterministic finite
automata. We identify how the characterizing pattern for level 1/2 of the
dot-depth hierarchy appears as a building block in the pattern characterizing
level 3/2 of this hierarchy, and continue this formation procedure with a
generalized iteration rule IT.
