Avoiding squares and overlaps over the natural numbers

DOI10.1016/J.DISC.2009.06.004MaRDI QIDQ1045019zbMATH OpenOpenAlexFDO

Authors Mathieu Guay-Paquet, Jeffrey Shallit

Publication date 15 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

combinatorics on wordspattern avoidanceinfinite alphabet

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(11)

• The lexicographically least square-free word with a given prefix
• 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

Describes a project that uses

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)