Geodesic
On minimal words with given subword complexity
The electronic journal of combinatorics, Tome 5 (1998)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We prove that the minimal length of a word $S_n$ having the property that it contains exactly $F_{m+2}$ distinct subwords of length $m$ for $1 \leq m \leq n$ is $F_n + F_{n+2}$. Here $F_n$ is the $n$th Fibonacci number defined by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n > 2$. We also give an algorithm that generates a minimal word $S_n$ for each $n \geq 1$.
DOI : 10.37236/1373
Classification : 68R15, 05C35
Mots-clés : minimal length of a word 
@article{10_37236_1373,
     author = {Ming-wei Wang and Jeffrey Shallit},
     title = {On minimal words with given subword complexity},
     journal = {The electronic journal of combinatorics},
     year = {1998},
     volume = {5},
     doi = {10.37236/1373},
     zbl = {0898.68058},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1373/}
}
TY  - JOUR
AU  - Ming-wei Wang
AU  - Jeffrey Shallit
TI  - On minimal words with given subword complexity
JO  - The electronic journal of combinatorics
PY  - 1998
VL  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1373/
DO  - 10.37236/1373
ID  - 10_37236_1373
ER  - 
%0 Journal Article
%A Ming-wei Wang
%A Jeffrey Shallit
%T On minimal words with given subword complexity
%J The electronic journal of combinatorics
%D 1998
%V 5
%U http://geodesic.mathdoc.fr/articles/10.37236/1373/
%R 10.37236/1373
%F 10_37236_1373
Ming-wei Wang; Jeffrey Shallit. On minimal words with given subword complexity. The electronic journal of combinatorics, Tome 5 (1998). doi: 10.37236/1373

Cité par Sources :