ALMOST OVERLAP-FREE WORDS AND THE WORD PROBLEM FOR THE FREE BURNSIDE SEMIGROUP SATISFYING x2= x3
A. N. Plyushchenko, Arseny M. Shur · International Journal of Algebra and Computation · 2011
We study the word problem for the free Burnside semigroup satisfying x2= x3and 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.