Games, equations and dot-depth two monoids (Q1201097)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Games, equations and dot-depth two monoids |
scientific article |
Statements
Games, equations and dot-depth two monoids (English)
0 references
17 January 1993
0 references
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.
0 references
dot-depth hierarchy
0 references
class of congruences
0 references
free monoids
0 references
Ehrenfeucht- Fraisse game
0 references