Some Forbidden Patterns in Automata for Dot-Depth One Languages
Heinz Schmitz · 2007
We deal with the class B 1 of dot-depth one languages which forms level one of the so-called dot-depth hierarchy. For some fixed alphabet A with jAj 2, a language L ` A + is in the class B 1 if and only if it can be expressed as a Boolean combination of languages u 0 A u 1 A u 2 A \\Delta \\Delta \\Delta A un\\Gamma1 A un , where u i 2 A and n 0. This class is the highest level of the dot-depth hierarchy known to be decidable up to now and a number of different characterizations are known. We add here one more in terms of certain patterns that must not appear in the transition graph of deterministic finite automata accepting dot-depth one languages. More precisely, the following levelwise characterization of languages having dot-depth one is known (k 0): A language L ` A + is in the class B 1;k if and only if any infinite sequence of words, where each word is a so-called k-extension of its predecessor, has a finite number of alternations with respect to L. It holds...