This article is cited in 4 papers

RESEARCH ARTICLE

The word problem in Hanoi Towers groups

Ievgen Bondarenko

Department of Algebra and Mathematical Logic, Mechanics and Mathematics Faculty, National Taras Shevchenko University of Kyiv, vul.Volodymyrska 64, 01033, Kyiv, Ukraine

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.

MSC: 68R05, 20F10

Received: 27.03.2014
Revised: 27.03.2014

Language: English

Bibliographic databases:

•