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

McCammond, J.

Int. J. Algebra Comput. 1, No. 1, 1-32 (1991).

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}}\).

Reviewer: D.Krob (Mont-Saint-Aignan)

MSC:

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

Keywords:

Green relation; finite automaton; alphabet; decidable word problem; presentation; Burnside semigroups; maximal subgroups