Some logical characterizations of the dot-depth hierarchy and applications. (English) Zbl 0831.68066

Blanchet-Sadri, F.

J. Comput. Syst. Sci. 51, No. 2, 324-337 (1995).

Summary: A logical characterization of natural subhierarchies of the dot-depth hierarchy refining a theorem of Thomas and a congruence characterization related to a version of the Ehrenfeucht-Fraïssé game generalizing a theorem of Simon are given. For a sequence \(\overline m = (m_1, \ldots, m_k)\) of positive integers, subclasses \({\mathcal L} (m_1, \ldots, m_k)\) of languages of level \(k\) are defined. \({\mathcal L} (m_1, \ldots, m_k)\) are shown to be decidable. Some properties of the characterizing congurences are studied, among them, a condition which insures \({\mathcal L} (m_1, \ldots, m_k)\) to be included in \({\mathcal L} (m_1', \ldots, m_k')\). A conjecture of Pin concerning tree hierarchies of monoids (the dot-depth being a particular case) is shown to be false.

MSC:

68Q70	Algebraic theory of languages and automata
68Q45	Formal languages and automata

Keywords:

dot-depth hierarchy