Almost overlap-free words and the word problem for the free burnside semigroup satisfying x2 = x3
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
Almost overlap-free words and the word problem for the free burnside semigroup satisfying x2 = x3
|
|
| Автор |
Plyushchenko, A. N.
Shur, A. M. |
|
| Тематика |
ALMOST OVERLAP-FREE WORDS
FREE BURNSIDE SEMIGROUP THE WORD PROBLEM THUE-MORSE SEQUENCE |
|
| Описание |
We study the word problem for the free Burnside semigroup satisfying x 2 = x3 and having two generators. The elements of this semigroup are classes of equivalent words. A natural way to solve the word problem is to select a unique "canonical" representative for each equivalence class. We prove that overlap-free words and "almost" overlap-free words can serve as canonical representatives of their equivalence classes. We show that such a word in a given class, if any, can be efficiently found. As a result, we construct a linear-time algorithm that partially solves the word problem for the semigroup under consideration. © 2011 World Scientific Publishing Company.
|
|
| Дата |
2024-04-24T12:38:28Z
2024-04-24T12:38:28Z 2011 |
|
| Тип |
Article
Journal article (info:eu-repo/semantics/article) info:eu-repo/semantics/submittedVersion |
|
| Идентификатор |
Plyushchenko, A. N., & Shur, A. M. (2011). ALMOST OVERLAP-FREE WORDS AND THE WORD PROBLEM FOR THE FREE BURNSIDE SEMIGROUP SATISFYING x2= x3. International Journal of Algebra and Computation, 21(06), 973–1006. doi:10.1142/s0218196711006558
0218-1967 Final All Open Access, Green https://arxiv.org/pdf/1102.4315 http://elar.urfu.ru/handle/10995/132615 10.1142/S0218196711006558 85013213529 000389513900053 |
|
| Язык |
en
|
|
| Права |
Open access (info:eu-repo/semantics/openAccess)
|
|
| Формат |
application/pdf
|
|
| Издатель |
World Scientific Pub Co Pte Ltd
|
|
| Источник |
International Journal of Algebra and Computation
International Journal of Algebra and Computation |
|