The word problem in Hanoi Towers groups

• Datum: 2018
• 1. Verfasser: Bondarenko, Ievgen
• Format: Artikel
• Sprache: Englisch
• Veröffentlicht: Lugansk National Taras Shevchenko University 2018
• Schlagworte: the Tower of Hanoi game; automaton group; word problem; complexity; 68R05; 20F10
• Online Zugang: https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1034
• Назва журналу: Algebra and Discrete Mathematics

We prove that the elements of the Hanoi Towers groups \(\mathcal{H}_m\) have depth bounded from above by a poly-logarithmic function \(O(\log^{m-2} n)\), where \(n\) is the length of an element. Therefore the word problem in groups \(\mathcal{H}_m\) is solvable in subexponential time \(exp(O(\log^{m...