Geodesic
The lexicographically least square-free word with a given prefix
Siddharth Berera1 ; Andrés Gómez-Colunga2 ; Joey Lakerdas-Gayle3 ; John López4 ; Mauditra Matin5 ; Daniel Roebuck6 ; Eric Rowland7 ; Noam Scully8 ; Juliet Whidden9
1University of Edinburgh
2Pennsylvania State University
3University of Waterloo
4Tulane University
5Delft University of Technology
6University of St Andrews
7Hofstra University
8Yale University
9Vassar College
The electronic journal of combinatorics, Tome 30 (2023) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The lexicographically least square-free infinite word on the alphabet of non-negative integers with a given prefix $p$ is denoted $L(p)$. When $p$ is the empty word, this word was shown by Guay-Paquet and Shallit to be the ruler sequence. For other prefixes, the structure is significantly more complicated. In this paper, we show that $L(p)$ reflects the structure of the ruler sequence for several words $p$. We provide morphisms that generate $L(n)$ for letters $n=1$ and $n\geq3$, and $L(p)$ for most families of two-letter words $p$.
DOI : 10.37236/11659
Classification : 68R15
Mots-clés : square-free word, ruler sequence, Zimin word, infinibonacci word

Siddharth Berera  1   ; Andrés Gómez-Colunga  2   ; Joey Lakerdas-Gayle  3   ; John López  4   ; Mauditra Matin  5   ; Daniel Roebuck  6   ; Eric Rowland  7   ; Noam Scully  8   ; Juliet Whidden  9

1 University of Edinburgh
2 Pennsylvania State University
3 University of Waterloo
4 Tulane University
5 Delft University of Technology
6 University of St Andrews
7 Hofstra University
8 Yale University
9 Vassar College 
@article{10_37236_11659,
     author = {Siddharth Berera and Andr\'es G\'omez-Colunga and Joey Lakerdas-Gayle and John L\'opez and Mauditra Matin and Daniel Roebuck and Eric Rowland and Noam Scully and Juliet Whidden},
     title = {The lexicographically least square-free word with a given prefix},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {3},
     doi = {10.37236/11659},
     zbl = {1537.68159},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11659/}
}
TY  - JOUR
AU  - Siddharth Berera
AU  - Andrés Gómez-Colunga
AU  - Joey Lakerdas-Gayle
AU  - John López
AU  - Mauditra Matin
AU  - Daniel Roebuck
AU  - Eric Rowland
AU  - Noam Scully
AU  - Juliet Whidden
TI  - The lexicographically least square-free word with a given prefix
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11659/
DO  - 10.37236/11659
ID  - 10_37236_11659
ER  - 
%0 Journal Article
%A Siddharth Berera
%A Andrés Gómez-Colunga
%A Joey Lakerdas-Gayle
%A John López
%A Mauditra Matin
%A Daniel Roebuck
%A Eric Rowland
%A Noam Scully
%A Juliet Whidden
%T The lexicographically least square-free word with a given prefix
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/11659/
%R 10.37236/11659
%F 10_37236_11659
Siddharth Berera; Andrés Gómez-Colunga; Joey Lakerdas-Gayle; John López; Mauditra Matin; Daniel Roebuck; Eric Rowland; Noam Scully; Juliet Whidden. The lexicographically least square-free word with a given prefix. The electronic journal of combinatorics, Tome 30 (2023) no. 3. doi: 10.37236/11659

Cité par Sources :