The word problem in Hanoi Towers groups
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...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Lugansk National Taras Shevchenko University
2018
|
| Теми: | |
| Онлайн доступ: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1034 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Algebra and Discrete Mathematics |
Репозитарії
Algebra and Discrete Mathematics| id |
oai:ojs.admjournal.luguniv.edu.ua:article-1034 |
|---|---|
| record_format |
ojs |
| spelling |
oai:ojs.admjournal.luguniv.edu.ua:article-10342018-04-26T02:11:00Z The word problem in Hanoi Towers groups Bondarenko, Ievgen the Tower of Hanoi game, automaton group, word problem, complexity 68R05, 20F10 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))\). Lugansk National Taras Shevchenko University 2018-04-26 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1034 Algebra and Discrete Mathematics; Vol 17, No 2 (2014) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1034/557 Copyright (c) 2018 Algebra and Discrete Mathematics |
| institution |
Algebra and Discrete Mathematics |
| collection |
OJS |
| language |
English |
| topic |
the Tower of Hanoi game automaton group word problem complexity 68R05 20F10 |
| spellingShingle |
the Tower of Hanoi game automaton group word problem complexity 68R05 20F10 Bondarenko, Ievgen The word problem in Hanoi Towers groups |
| topic_facet |
the Tower of Hanoi game automaton group word problem complexity 68R05 20F10 |
| format |
Article |
| author |
Bondarenko, Ievgen |
| author_facet |
Bondarenko, Ievgen |
| author_sort |
Bondarenko, Ievgen |
| title |
The word problem in Hanoi Towers groups |
| title_short |
The word problem in Hanoi Towers groups |
| title_full |
The word problem in Hanoi Towers groups |
| title_fullStr |
The word problem in Hanoi Towers groups |
| title_full_unstemmed |
The word problem in Hanoi Towers groups |
| title_sort |
word problem in hanoi towers groups |
| description |
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))\). |
| publisher |
Lugansk National Taras Shevchenko University |
| publishDate |
2018 |
| url |
https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1034 |
| work_keys_str_mv |
AT bondarenkoievgen thewordprobleminhanoitowersgroups AT bondarenkoievgen wordprobleminhanoitowersgroups |
| first_indexed |
2024-04-12T06:26:42Z |
| last_indexed |
2024-04-12T06:26:42Z |
| _version_ |
1796109188362928128 |