zbMATH — the first resource for mathematics

The solution to the word problem for the relatively free semigroups satisfying \(T^ a=T^{a+b}\) with a\(\geq 6\). (English) Zbl 0732.20034
Let A be an alphabet and let \(a\geq 0\), \(b\geq 1\) be two integers. Then the associated Burnside semigroup is the semigroup denoted by \(B_ A(a,b)\) and defined by the presentation \[ B_ A(a,b)=<A;\quad t^ a=t^{a+b}\text{ for } every\quad t\in A^*>. \] It is a very old problem to know if the word problem is decidable or not for this class of semigroups. The only known result is due to A. De Luca and S. Varricchio who proved that \(B_ A(a,1)\) with \(a\geq 5\) has a decidable word problem.
The author solves quite entirely the above problem by proving the decidability of the word problem for \(B_ A(a,b)\) with \(a\geq 6\). The proof relies on a very long effective construction of an automaton str(w) that regocnizes the set of the words equivalent to w with respect to the above presentation of \(B_ A(a,b)\). The method used by the author allows him also obtain several structure results for Burnside semigroups. For instance, he proves that \(B_ A(a,b)\) is finite \({\mathcal J}\) above when \(a\geq 6\). It is also shown that the maximal subgroups of \(B_ A(a,b)\) are all isomorphic to the cyclic group \({\mathbb{Z}}/b{\mathbb{Z}}\).

20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
03D40 Word problems, etc. in computability and recursion theory
68Q70 Algebraic theory of languages and automata
68W30 Symbolic computation and algebraic computation
Full Text: DOI