The word problem in Hanoi Towers groups

Abstract

We prove that 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))$.

Cited by in corpus (1)

• On the Complexity of the Word Problem for Automaton Semigroups and Automaton Groups