Bordered Conjugates of Words over Large Alphabets

  • Tero Harju
  • Dirk Nowotka

Abstract

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.

Published
2008-11-24
Article Number
N41