Geodesic
The word problem in Hanoi Towers groups
Algebra and discrete mathematics, Tome 17 (2014) no. 2, pp. 248-255.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, word problem, complexity.
Mots-clés : automaton group 
@article{ADM_2014_17_2_a5,
     author = {Ievgen Bondarenko},
     title = {The word problem in {Hanoi} {Towers} groups},
     journal = {Algebra and discrete mathematics},
     pages = {248--255},
     publisher = {mathdoc},
     volume = {17},
     number = {2},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADM_2014_17_2_a5/}
}
TY  - JOUR
AU  - Ievgen Bondarenko
TI  - The word problem in Hanoi Towers groups
JO  - Algebra and discrete mathematics
PY  - 2014
SP  - 248
EP  - 255
VL  - 17
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ADM_2014_17_2_a5/
LA  - en
ID  - ADM_2014_17_2_a5
ER  - 
%0 Journal Article
%A Ievgen Bondarenko
%T The word problem in Hanoi Towers groups
%J Algebra and discrete mathematics
%D 2014
%P 248-255
%V 17
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ADM_2014_17_2_a5/
%G en
%F ADM_2014_17_2_a5
Ievgen Bondarenko. The word problem in Hanoi Towers groups. Algebra and discrete mathematics, Tome 17 (2014) no. 2, pp. 248-255. http://geodesic.mathdoc.fr/item/ADM_2014_17_2_a5/

[1] I. Bondarenko, “Growth of Schreier graphs of automaton groups”, Mathematische Annalen, 354:2 (2012), 765–785 | DOI | MR | Zbl

[2] R. I. Grigorchuk, V. V. Nekrashevych, V. I. Sushchansky, “Automata, dynamical systems and groups”, Proceedings of the Steklov Institute of Mathematics, 231, 2000, 128–203 | MR | Zbl

[3] R. I. Grigorchuk, Z. Šuniḱ, “Asymptotic aspects of Schreier graphs and Hanoi Towers groups”, C. R. Math. Acad. Sci. Paris, 342:8 (2006), 545–550 | DOI | MR | Zbl

[4] R. I. Grigorchuk, Z. Šuniḱ, “Self-similarity and branching in group theory”, London Mathematical Society Lecture Note Series, 339, 2007, 36–95 | MR | Zbl

[5] A. M. Hinz, “The Tower of Hanoi”, Enseign. Math. (2), 35:3–4 (1989), 289–321 | MR | Zbl

[6] S. Klavzar, U. Milutinovic, C. Petr, “On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem”, Discrete Appl. Math., 120:1–3 (2002), 141–157 | DOI | MR | Zbl

[7] Y. Muntyan, D. Savchuk, AutomGrp — GAP package for computations in self-similar groups and semigroups, Version 1.1.2, 2008

[8] V. Nekrashevych, Self-similar groups, Mathematical Surveys and Monographs, 117, AMS, Providence, RI, 2005 | DOI | MR | Zbl

[9] M. Szegedy, “In how many steps the k peg version of the Towers of Hanoi game can be solved?”, STACS 99 (Trier), Lecture Notes in Comput. Sci., 1563, Springer, Berlin, 1999, 356–361 | DOI | MR