Games, equations and dot-depth-two monoids

Games, equations and dot-depth-two monoids

0.00 Avg rating0 Votes
Article ID: iaor19931112
Country: Netherlands
Volume: 39
Issue: 2
Start Page Number: 99
End Page Number: 111
Publication Date: Oct 1992
Journal: Discrete Applied Mathematics
Authors:
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 kof the Straubing hierarchy of aperiodic monoids can be characterized in terms of the monoidsA*/¸∼(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.

Reviews

Required fields are marked *. Your email address will not be published.