Almost overlap-free words and the word problem for the free burnside semigroup satisfying x2 = x3

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.