Some Logical Characterizations of the Dot-Depth Hierarchy and Applications

摘要

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 m=(m1, ..., mk) of positive integers, subclasses L(m1, ..., mk) of languages of level k are defined. L(m1, ..., mk) are shown to be decidable. Some properties of the characterizing congruences are studied, among them, a condition which insures L(m1, ..., mk) to be included in L(m′1, ..., m′k′). A conjecture of Pin concerning tree hierarchies of monoids (the dot-depth being a particular case) is shown to be false.