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.
Some Logical Characterizations of the Dot-Depth Hierarchy and Applications
PDF (Portable Document Format)
614 KB
Created on 8/2/2011
Views: 1790
Additional Information
- Publication
- Journal of Computer and System Sciences
- Language: English
- Date: 1995
- Keywords
- Computer Science, Dot-Depth Hierarchy