Avoiding large squares in infinite binary words

Details Avoiding large squares in infinite binary words Avoiding large squares in infinite binary words

2003-06-04

arxiv.org/abs/math/0306081v1

Mathematics

Combinatorics

Scientific paper

We consider three aspects of avoiding large squares in infinite binary words. First, we construct an infinite binary word avoiding both cubes xxx and squares yy with |y| >= 4; our construction is somewhat simpler than the original construction of Dekking. Second, we construct an infinite binary word avoiding all squares except 00, 11, and 0101; our construction is somewhat simpler than the original construction of Fraenkel and Simpson. In both cases, we also show how to modify our construction to obtain exponentially many words of length n with the given avoidance properties. Finally, we answer an open question of Prodinger and Urbanek from 1979 by demonstrating the existence of two infinite binary words, each avoiding arbitrarily large squares, such that their perfect shuffle has arbitrarily large squares.

Affiliated with

Also associated with

No associations

Rating

Avoiding large squares in infinite binary words 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 Avoiding large squares in infinite binary words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Avoiding large squares in infinite binary words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-129780