Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/112260
Title: Almost Overlap-free Words and the Word Problem for the Free Burnside Semigroup Satisfying x2 = x3
Authors: Plyushchenko, A. N.
Shur, A. M.
Issue Date: 2011
Publisher: World Scientific Pub Co Pte Lt
Citation: Plyushchenko A. N. Almost Overlap-free Words and the Word Problem for the Free Burnside Semigroup Satisfying x2 = x3 / A. N. Plyushchenko, A. M. Shur. — DOI 10.1016/j.solidstatesciences.2008.09.009 // International Journal of Algebra and Computation. — 2011. — Vol. 21. — Iss. 6. — P. 973-1006.
Abstract: 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.
Keywords: ALMOST OVERLAP-FREE WORDS
FREE BURNSIDE SEMIGROUP
THE WORD PROBLEM
THUE-MORSE SEQUENCE
URI: http://hdl.handle.net/10995/112260
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 80055081517
ISSN: 0218-1967
DOI: 10.1016/j.solidstatesciences.2008.09.009
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-80055081517.pdf335,14 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.