Decidable Hierarchies of Starfree Languages

Christian Glasser and Heinz Schmitz

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


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.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Start Conference Manager
Conference Systems