Avoiding squares and overlaps over the natural numbers

DOI10.1016/J.DISC.2009.06.004zbMATH Open1215.68193arXiv0901.1397OpenAlexW2079923544MaRDI QIDQ1045019FDOQ1045019

Authors: Mathieu Guay-Paquet, Jeffrey Shallit 

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0901.1397

Recommendations

• Extremal infinite overlap-free binary words
• Avoiding fractional powers over the natural numbers
• Avoidance of split overlaps
• Avoiding large squares in infinite binary words
• scientific article; zbMATH DE number 512830

zbMATH Keywords

combinatorics on wordspattern avoidanceinfinite alphabet

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• The ring of \(k\)-regular sequences
• Automatic Sequences
• Backtrack Programming
• Substitution dynamical systems on infinite alphabets
• Arithmetics properties of substitutions and infinite automata
• On the complexity of infinite words generated by countable \(q\)-automata
• The Towers of Hanoi and Binary Numerals

Cited In (11)

• Decision algorithms for Fibonacci-automatic words. II: Related sequences and avoidability
• Avoidance of split overlaps
• Avoiding 3/2-powers over the natural numbers
• Initial non-repetitive complexity of infinite words
• Avoiding fractional powers over the natural numbers
• Avoiding 5/4-Powers on the Alphabet of Nonnegative Integers (Extended Abstract)
• Morphisms on infinite alphabets, countable states automata and regular sequences
• Deleting terms of the divergent \(p\)-series and reciprocals of primes series using the Thue-Morse sequence
• Avoiding 5/4-powers on the alphabet of nonnegative integers
• Profinite automata
• The lexicographically least square-free word with a given prefix

Uses Software

• OEIS

This page was built for publication: Avoiding squares and overlaps over the natural numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1045019)