The word problem in Hanoi Towers groups

被引：0

作者：

Bondarenko, Ievgen ^{[1
]}

机构：

[1] Natl Tams Shevchenko Univ Kyiv, Mech & Math Fac, Dept Algebra & Math Log, Vul Volodymyrska 64, UA-11033 Kiev, Ukraine

来源：

ALGEBRA & DISCRETE MATHEMATICS | 2014年 / 17卷 / 02期

关键词：

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

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We prove that the elements of the Hanoi Towers groups H-m, have depth bounded from above by a poly-logarithmic function 0(log(m-2) n), where a is the length or an element. Therefore the word problem in groups H-m is solvable in subexponential tirne exp(O(log(m-2)n)).

引用

页码：248 / 255

页数：8

共 9 条

[1] Growth of Schreier graphs of automaton groups
Bondarenko, Ievgen V.
[J]. MATHEMATISCHE ANNALEN, 2012, 354 (02) : 765 - 785
[2] Asymptotic aspects of Schreier graphs and Hanoi Towers Groups
Grigorchuk, R
Sunik, Z
[J]. COMPTES RENDUS MATHEMATIQUE, 2006, 342 (08) : 545 - 550
[3] GRIGORCHUK R, 2007, LONDON MATH SOC LECT, V339, P36
[4] Grigorchuk R. I., 2000, P STEKLOV I MATH+, V231, P128
[5] Hinz A., 1989, LENSEIGNEMENT MATH M, V35, P289, DOI DOI 10.5169/SEALS-57378
[6] On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem
Klavzar, S
Milutinovic, U
Petr, C
[J]. DISCRETE APPLIED MATHEMATICS, 2002, 120 (1-3) : 141 - 157
[7] Muntyan Y., 2008, AUTOMGRP GAP PACKAGE
[8] Nekrashevych V. V, 2005, MATH SURVEYS MONOGRA, V117
[9] Szegedy M, 1999, LECT NOTES COMPUT SC, V1563, P356

← 1 →