RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Algebra Discrete Math.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Algebra Discrete Math., 2014, том 17, выпуск 2, страницы 248–255 (Mi adm469)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

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

Аннотация: 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))$.

Ключевые слова: the Tower of Hanoi game, automaton group, word problem, complexity.

Полный текст: PDF файл (123 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
MSC: 68R05, 20F10
Поступила в редакцию: 27.03.2014
Исправленный вариант: 27.03.2014
Язык публикации: английский

Образец цитирования: Ievgen Bondarenko, “The word problem in Hanoi Towers groups”, Algebra Discrete Math., 17:2 (2014), 248–255

Цитирование в формате AMSBIB
\RBibitem{Bon14}
\by Ievgen~Bondarenko
\paper The word problem in Hanoi Towers groups
\jour Algebra Discrete Math.
\yr 2014
\vol 17
\issue 2
\pages 248--255
\mathnet{http://mi.mathnet.ru/adm469}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3287932}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/adm469
  • http://mi.mathnet.ru/rus/adm/v17/i2/p248

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. D. D'Angeli, E. Rodaro, J. Ph. Waechter, “On the complexity of the word problem for automaton semigroups and automaton groups”, Adv. Appl. Math., 90 (2017), 160–187  crossref  mathscinet  zmath  isi  scopus
  • Algebra and Discrete Mathematics
    Просмотров:
    Эта страница:82
    Полный текст:36
    Литература:18

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019