×

Avoiding squares and overlaps over the natural numbers. (English) Zbl 1215.68193

Summary: 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\(\dots\), 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 \(\varphi : \mathbb N^* \to \mathbb N^*\) that generates the lexicographically least infinite overlap-free word by iteration. Furthermore, we show that for all \(h,k\in \mathbb N\) with \(h\leq k\), the word \(\varphi ^{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.

MSC:

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

Software:

OEIS

Online Encyclopedia of Integer Sequences:

An infinite overlap-free word without backtracking.

References:

[1] Allouche, J.-P.; Shallit, J., The ring of \(k\)-regular sequences, Theoret. Comput. Sci., 98, 2, 163-197 (1992) · Zbl 0774.68072
[2] Allouche, J.-P.; Shallit, J., Automatic Sequences: Theory, Applications, Generalizations (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1086.11015
[3] J. Berstel, Axel Thue’s Papers on Repetitions in Words: a Translation, no. 20 in Publications du Laboratoire de Combinatoire et d’Informatique Mathématique, Université du Québec à Montréal, 1995; J. Berstel, Axel Thue’s Papers on Repetitions in Words: a Translation, no. 20 in Publications du Laboratoire de Combinatoire et d’Informatique Mathématique, Université du Québec à Montréal, 1995
[4] Er, M. C., The Towers of Hanoi and binary numerals, J. Inf. Optim. Sci., 6, 2, 147-152 (1985) · Zbl 0578.68054
[5] Ferenczi, S., Substitution dynamical systems on infinite alphabets, Ann. Inst. Fourier (Grenoble), 56, 7, 2315-2343 (2006) · Zbl 1147.37007
[6] Golomb, S. W.; Baumert, L. D., Backtrack programming, J. Assoc. Comput. Mach., 12, 516-524 (1965) · Zbl 0139.12305
[7] Le Gonidec, M., Sur la complexité de mots infinis engendrés par des \(q\)-automates dénombrables, Ann. Inst. Fourier (Grenoble), 56, 7, 2463-2491 (2006) · Zbl 1121.68090
[8] Mauduit, C., Propriétés arithmétiques des substitutions et automates infinis, Ann. Inst. Fourier (Grenoble), 56, 7, 2525-2549 (2006) · Zbl 1147.11016
[9] N.J.A. Sloane, The on-line encyclopedia of integer sequences, 2008. http://www.research.att.com/ njas/sequences/; N.J.A. Sloane, The on-line encyclopedia of integer sequences, 2008. http://www.research.att.com/ njas/sequences/ · Zbl 1274.11001
[10] Thue, A., Über unendliche Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl., 7, 1-22 (1906), (reprinted in T. Nagell (Ed.), Selected Mathematical Papers of Axel Thue, Universitetsforlaget, Oslo, 1977, pp. 139-158) · JFM 39.0283.01
[11] Thue, A., Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl., 1, 1-67 (1912), (reprinted in T. Nagell (Ed.), Selected Mathematical Papers of Axel Thue, Universitetsforlaget, Oslo, 1977, pp. 413-478) · JFM 44.0462.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.