Bordered conjugates of words over large alphabets

Tero Harju ; Dirk Nowotka

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

The border correlation function attaches to every word $w$ a binary word $\beta(w)$ of the same length where the $i$th letter tells whether the $i$th conjugate $w' = vu$ of $w =uv$ is bordered or not. Let $[{u}]$ denote the set of conjugates of the word $w$. We show that for a 3-letter alphabet $A$, the set of $\beta$-images equals $\beta(A^n) = B^* \setminus \left([{ab^{n-1}}] \cup D\right)$ where $D=\{a^n\}$ if $n \in \{5,7,9,10,14,17\}$, and otherwise $D=\emptyset$. Hence the number of $\beta$-images is $B^n_3=2^n-n-m$, where $m=1$ if $n\in \{5,7,9,10,14,17\}$ and $m=0$ otherwise.

Détail

DOI : 10.37236/916

Classification : 68R15
Mots-clés : combinatorics on words, border correlation, binary words, square-free, cycli-