|
Algebra and Discrete Mathematics, 2014, Volume 17, Issue 2, Pages 248–255
(Mi adm469)
|
|
|
|
This article is cited in 4 scientific papers (total 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.
Received: 27.03.2014 Revised: 27.03.2014
Citation:
Ievgen Bondarenko, “The word problem in Hanoi Towers groups”, Algebra Discrete Math., 17:2 (2014), 248–255
Linking options:
https://www.mathnet.ru/eng/adm469 https://www.mathnet.ru/eng/adm/v17/i2/p248
|
Statistics & downloads: |
Abstract page: | 186 | Full-text PDF : | 104 | References: | 34 |
|