Games, equations and dot-depth two monoids

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: Given any finite alphabet A and positive integers m1, …, mk, congruences on A*, denoted by ~(m1, …, mk) and related to a version of the Ehrenfeucht-Fraisse game, are defined. Level k of the Straubing hierarchy of aperiodic monoids can be characterized in terms of the monoids A*/~(m1, … mk). A natural subhierarchy of level 2 and equation systems satisfied in the corresponding varieties of monoids are defined. For A = 2, a necessary and sufficient condition is given for A*/~(m1, … , mk) to be of dot-depth exactly 2. Upper and lower bounds on the dot-depth of the A*/~(m1, … mk) are discussed.

Additional Information

Publication
Discrete Applied Mathematics
Language: English
Date: 1992
Keywords
Computer Science, Games, Monoids