Some Logical Characterizations of the Dot-Depth Hierarchy and Applications

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Francine Blanchet-Sadri, Professor (Creator)
The University of North Carolina at Greensboro (UNCG )
Web Site:

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

Additional Information

Journal of Computer and System Sciences
Language: English
Date: 1995
Computer Science, Dot-Depth Hierarchy