The word problem in Hanoi Towers groups
We prove that the elements of the Hanoi Towers groups Hm have depth bounded from above by a poly-logarithmic function O(logm⁻²n), where n is the length of an element. Therefore the word problem in groups Hm is solvable in subexponential time exp(O(logm⁻²n)).
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2014 |
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2014
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/153336 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | The word problem in Hanoi Towers groups / I. Bondarenko // Algebra and Discrete Mathematics. — 2014. — Vol. 17, № 2. — С. 248–255. — Бібліогр.: 9 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862722873343344640 |
|---|---|
| author | Bondarenko, I. |
| author_facet | Bondarenko, I. |
| citation_txt | The word problem in Hanoi Towers groups / I. Bondarenko // Algebra and Discrete Mathematics. — 2014. — Vol. 17, № 2. — С. 248–255. — Бібліогр.: 9 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | We prove that the elements of the Hanoi Towers groups Hm have depth bounded from above by a poly-logarithmic function O(logm⁻²n), where n is the length of an element. Therefore the word problem in groups Hm is solvable in subexponential time exp(O(logm⁻²n)).
|
| first_indexed | 2025-12-07T18:38:22Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-153336 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-07T18:38:22Z |
| publishDate | 2014 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Bondarenko, I. 2019-06-14T03:23:12Z 2019-06-14T03:23:12Z 2014 The word problem in Hanoi Towers groups / I. Bondarenko // Algebra and Discrete Mathematics. — 2014. — Vol. 17, № 2. — С. 248–255. — Бібліогр.: 9 назв. — англ. 1726-3255 2010 MSC:68R05, 20F10. https://nasplib.isofts.kiev.ua/handle/123456789/153336 We prove that the elements of the Hanoi Towers groups Hm have depth bounded from above by a poly-logarithmic function O(logm⁻²n), where n is the length of an element. Therefore the word problem in groups Hm is solvable in subexponential time exp(O(logm⁻²n)). en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics The word problem in Hanoi Towers groups Article published earlier |
| spellingShingle | The word problem in Hanoi Towers groups Bondarenko, I. |
| title | 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_short | The word problem in Hanoi Towers groups |
| title_sort | word problem in hanoi towers groups |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/153336 |
| work_keys_str_mv | AT bondarenkoi thewordprobleminhanoitowersgroups AT bondarenkoi wordprobleminhanoitowersgroups |