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)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

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

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