The word problem in Hanoi Towers groups

Ievgen Bondarenko

Abstract


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


Keywords


the Tower of Hanoi game, automaton group, word problem, complexity

Full Text:

PDF

Refbacks

  • There are currently no refbacks.