The Simplest Binary Word With Only Three Squares
RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 3

We re-examine previous constructions of infinite binary words containing few distinct squares with the goal of finding the “simplest”, in a certain sense. We exhibit several new constructions. Rather than using tedious case-based arguments to prove that the constructions have the desired property, we rely instead on theorem-proving software for their correctness.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ita/2021001
Classification : 68R15 
@article{ITA_2021__55_1_A5_0,
     author = {Gabric, Daniel and Shallit, Jeffrey},
     title = {The {Simplest} {Binary} {Word} {With} {Only} {Three} {Squares}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ita/2021001},
     mrnumber = {4245320},
     zbl = {1492.68113},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2021001/}
}
TY  - JOUR
AU  - Gabric, Daniel
AU  - Shallit, Jeffrey
TI  - The Simplest Binary Word With Only Three Squares
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2021
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2021001/
DO  - 10.1051/ita/2021001
LA  - en
ID  - ITA_2021__55_1_A5_0
ER  - 
%0 Journal Article
%A Gabric, Daniel
%A Shallit, Jeffrey
%T The Simplest Binary Word With Only Three Squares
%J RAIRO. Theoretical Informatics and Applications
%D 2021
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2021001/
%R 10.1051/ita/2021001
%G en
%F ITA_2021__55_1_A5_0
Gabric, Daniel; Shallit, Jeffrey. The Simplest Binary Word With Only Three Squares. RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 3. doi: 10.1051/ita/2021001

[1] G. Badkobeh, Infinite words containing the minimal number of repetitions. J. Discrete Algorithms 20 (2013) 38–42. | MR | Zbl | DOI

[2] G. Badkobeh and M. Crochemore, Fewest repetitions in infinite binary words. RAIRO: ITA 46 (2012) 17–31. | MR | Zbl | Numdam

[3] J. Berstel, Sur la construction de mots sans carré. Séminaire de Théorie des Nombres (1978–1979) 18.01–18.15. | MR | Zbl

[4] J. Berstel, Axel Thue’s Papers on Repetitions in Words: a Translation. Number 20 in Publications du Laboratoire de Combinatoire et d’Informatique Mathématique. Université du Québec à Montréal (1995).

[5] F. Blanchet-Sadri, J. Currie, N. Rampersad and N. Fox, Abelian complexity of fixed point of morphism 0↦012, 1↦02, 2↦1. INTEGERS: Elect. J. Combin. Number Theory 14 (2014) #A11 (electronic). | MR | Zbl

[6] É. Charlier, N. Rampersad and J. Shallit, Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comp. Sci. 23 (2012) 1035–1066. | MR | Zbl | DOI

[7] A. Cobham, Uniform tag sequences. Math. Systems Theory 6 (1972) 164–192. | MR | Zbl | DOI

[8] R. C. Entringer, D. E. Jackson and J. A. Schatz, On nonrepetitive sequences. J. Combin. Theory Ser. A 16 (1974) 159–164. | MR | Zbl | DOI

[9] A. S. Fraenkel and J. Simpson, How many squares must a binary sequence contain ? Electronic J. Combinatorics 2 (1994) #R2. | MR | Zbl | DOI

[10] T. Harju and D. Nowotka, Binary words with few squares. Bull. European Assoc. Theor. Comput. Sci. 89 (2006) 164–166. | MR | Zbl

[11] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979). | MR | Zbl

[12] H. Mousavi, Automatic theorem proving in Walnut (2016). | arXiv

[13] P. Ochem, A generator of morphisms for infinite words. RAIRO: ITA 40 (2006) 427–441. | MR | Zbl | Numdam

[14] N. Rampersad, J. Shallit and M.-W. Wang, Avoiding large squares in infinite binary words. Theoret. Comput. Sci. 339 (2005) 19–34. | MR | Zbl | DOI

[15] A. Thue, Über unendliche Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906) 1–22. Reprinted in Selected Mathematical Papers of Axel Thue, edited by T. Nagell, Universitetsforlaget, Oslo (1977) 139–158. | MR | JFM

[16] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1–67. Reprinted in Selected Mathematical Papers of Axel Thue, edited by T. Nagell, Universitetsforlaget, Oslo (1977) 413–478. | JFM

Cité par Sources :

Research of the second author is supported by NSERC grant 2018-04118.