ALMOST OVERLAP-FREE WORDS AND THE WORD PROBLEM FOR THE FREE BURNSIDE SEMIGROUP SATISFYING x(2) = x(3) / Plyushchenko Andrey N.,Shur Arseny M. // INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION. - 2011. - V. 21, l. 6. - P. 973-1006.

ISSN/EISSN:

0218-1967 / нет данных

Type:

Article

Abstract:

We study the word problem for the free Burnside semigroup satisfying x(2) = x(3) 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.

Author keywords:

Free Burnside semigroup; the word problem; almost overlap-free words; Thue-Morse sequence

DOI:

10.1142/S0218196711006558

Web of Science ID:

ISI:000296620300008

Соавторы в МНС:

Другие поля

Поле	Значение
Month	SEP
Publisher	WORLD SCIENTIFIC PUBL CO PTE LTD
Address	5 TOH TUCK LINK, SINGAPORE 596224, SINGAPORE
Language	English
Research-Areas	Mathematics
Web-of-Science-Categories	Mathematics
Author-Email	mathplush@yandex.ru aimsure@mail.ru
Number-of-Cited-References	14
Usage-Count-Last-180-days	2
Usage-Count-Since-2013	18
Journal-ISO	Int. J. Algebr. Comput.
Doc-Delivery-Number	842SL