The solution to the word problem for the relatively free semigroups satisfying \(T^ a=T^{a+b}\) with a\(\geq 6\).

*(English)*Zbl 0732.20034Let 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}}\).

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 |