Games, equations and dot-depth two monoids (Q1201097)

Some questions concerning the dot-depth hierarchy \({\mathcal V}_ k\) and its sub-hierarchies \({\mathcal V}_{k,m}\) are studied. The approach taken by the author is based on a class of congruences \(\sim \overline{m}\) defined on free monoids for every sequence \(\overline{m} = (m_ 1,\dots,m_ k)\) of positive integers. Such congruences arise from an extension of the standard Ehrenfeucht-Fraisse game due to W. Thomas. The author provides some systems of equations which are satisfied by \({\mathcal V}_{2,m}\), and for an alphabet \(A\) of cardinality at least two obtains, amongst other things, necessary and sufficient conditions for \(A^*/\sim (m_ 1,\dots,m_ k)\) to be of dot-depth exactly 2.