Decidability problems in automaton semigroups

Abstract

We consider decidability problems in self-similar semigroups, and in particular in semigroups of automatic transformations of $X^{\ast }$. We describe algorithms answering the word problem, and bound its complexity under some additional assumptions. We give a partial algorithm that decides in a group generated by an automaton, given $x,y$, whether an Engel identity ($[\cdots [[x,y],y],\dots ,y]=1$ for a long enough commutator sequence) is satisfied. This algorithm succeeds, importantly, in proving that Grigorchuk's $2$-group is not Engel. We consider next the problem of recognizing Engel elements, namely elements $y$ such that the map $x\mapsto [x,y]$ attracts to $\{1\}$. Although this problem seems intractable in general, we prove that it is decidable for Grigorchuk's group: Engel elements are precisely those of order at most $2$. We include, in the text, a large number of open problems. Our computations were implemented using the package "Fr" within the computer algebra system "Gap".

arXiv admin note: text overlap with arXiv:1512.01717

References in corpus (1)

• The 2-dimension series of the just-nonsolvable BSV group

Cited by in corpus (1)

• A note on Engel elements in the first Grigorchuk group