Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x^2=x^3

Details Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x^2=x^3 Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x^2=x^3

2011-02-21

arxiv.org/abs/1102.4315v1

Computer Science

Formal Languages and Automata Theory

33 pages, submitted to Internat. J. of Algebra and Comput

Scientific paper

In this paper we investigate the word problem of the free Burnside semigroup satisfying x^2=x^3 and having two generators. 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 so-called almost overlap-free words (this notion is some generalization of the notion of overlap-free words) can serve as canonical representatives for corresponding 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.

Affiliated with

Also associated with

No associations

Rating

Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x^2=x^3 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x^2=x^3, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x^2=x^3 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521101