Name
Abstract | ||
|---|---|---|
We consider decidability problems in self-similar semigroups, and in particular in semigroups of automatic transformations of $X^*$. 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 Grigorchuku0027s $2$-group is not Engel. We consider next the problem of recognizing Engel elements, namely elements $y$ such that the map $xmapsto[x,y]$ attracts to ${1}$. Although this problem seems intractable in general, we prove that it is decidable for Grigorchuku0027s 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. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Logic in Computer Science | Discrete mathematics,Word problem (mathematics education),Automaton,Symbolic computation,Algorithm,Decidability,Commutator (electric),Mathematics,Computation |
DocType | Volume | Citations |
Journal | abs/1705.04598 | 0 |
PageRank | References | Authors |
0.34 | 3 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laurent Bartholdi | 1 | 27 | 8.74 |