The dot-depth of a generating class of aperiodic monoids is computable. (English) Zbl 0776.68087

Blanchet-Sadri, F.

Int. J. Found. Comput. Sci. 3, No. 4, 419-442 (1992).

A regular language is star-free if it can be constructed from finite languages by Boolean operations and concatenations. Among the other characterizations of this family of languages, the theorem of M. P. Schützenberger is of special importance: a regular language is star- free iff its syntactic monoid is aperiodic. In Brzozowski’s dot-depth hierarchy, star-free languages are classified according to the number of alternations of Boolean operations and concatenations needed in their construction. A relatively long-standing questions is whether one always can determine the place of a given star-free language in this hierarchy. Here a closely related hierarchy introduced by H. Straubing is considered. Corresponding to this hierarchy, there is a hierarchy (+) \(V_ 0\subset V_ 1\subset\dots\) of varieties of finite monoids, and the original problem is equivalent to determining the place of a finite aperiodic monoid in this hierarchy. Each variety \(V_ k\) is generated by the monoids \(A^*/\sim_{\mathbf{m}}\), where \(A\) is a finite alphabet and \(\sim_{\mathbf{m}}\) is a congruence defined by a \(k\)-tuple m of positive integers. W. Thomas has shown that these congruences are also defined by certain semantic games on words. By using these games for a thorough analysis of the congruences \(\sim_{\mathbf{m}}\), the author shows that the exact places of the monoids \(A^*/\sim_{\mathbf{m}}\) in (+) can be found.

Reviewer: M.Steinby (Turku)

MSC:

68Q70	Algebraic theory of languages and automata
20M35	Semigroups in automata theory, linguistics, etc.
68Q45	Formal languages and automata

Keywords:

regular language; syntactic monoid; dot-depth hierarchy; star-free languages; varieties of finite monoids; semantic games