Geodesic
Weakly self-avoiding words and a construction of Friedman
The electronic journal of combinatorics, Tome 8 (2001) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

H. Friedman obtained remarkable results about the longest finite sequence $x$ over a finite alphabet such that for all $i \ne j$ the word $x[i..2i]$ is not a subsequence of $x[j..2j]$. In this note we consider what happens when "subsequence" is replaced by "subword"; we call such a sequence a "weakly self-avoiding word". We prove that over an alphabet of size $1$ or $2$, there is an upper bound on the length of weakly self-avoiding words, while if the alphabet is of size $3$ or more, there exists an infinite weakly self-avoiding word.
DOI : 10.37236/1587
Classification : 68R15
Mots-clés : weakly self-avoiding word 
@article{10_37236_1587,
     author = {Jeffrey Shallit and Ming-wei Wang},
     title = {Weakly self-avoiding words and a construction of {Friedman}},
     journal = {The electronic journal of combinatorics},
     year = {2001},
     volume = {8},
     number = {1},
     doi = {10.37236/1587},
     zbl = {0966.68164},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1587/}
}
TY  - JOUR
AU  - Jeffrey Shallit
AU  - Ming-wei Wang
TI  - Weakly self-avoiding words and a construction of Friedman
JO  - The electronic journal of combinatorics
PY  - 2001
VL  - 8
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1587/
DO  - 10.37236/1587
ID  - 10_37236_1587
ER  - 
%0 Journal Article
%A Jeffrey Shallit
%A Ming-wei Wang
%T Weakly self-avoiding words and a construction of Friedman
%J The electronic journal of combinatorics
%D 2001
%V 8
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1587/
%R 10.37236/1587
%F 10_37236_1587
Jeffrey Shallit; Ming-wei Wang. Weakly self-avoiding words and a construction of Friedman. The electronic journal of combinatorics, Tome 8 (2001) no. 1. doi: 10.37236/1587

Cité par Sources :