Avoiding Squares and Overlaps Over the Natural Numbers

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

16 pages, 2 tables

Scientific paper

We consider avoiding squares and overlaps over the natural numbers, using a greedy algorithm that chooses the least possible integer at each step; the word generated is lexicographically least among all such infinite words. In the case of avoiding squares, the word is 01020103..., the familiar ruler function, and is generated by iterating a uniform morphism. The case of overlaps is more challenging. We give an explicitly-defined morphism phi : N* -> N* that generates the lexicographically least infinite overlap-free word by iteration. Furthermore, we show that for all h,k in N with h <= k, the word phi^{k-h}(h) is the lexicographically least overlap-free word starting with the letter h and ending with the letter k, and give some of its symmetry properties.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Avoiding Squares and Overlaps Over the Natural Numbers 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 Squares and Overlaps Over the Natural Numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Avoiding Squares and Overlaps Over the Natural Numbers will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-531897

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.