Abstract

The border correlation function attaches to every word w a binary word β(w) of the same length where the ith letter tells whether the ith 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 β-images equals β(Aⁿ) = B^∗ − ([abⁿ⁻¹ ∪ D) where D = {aⁿ} if n ∈ {5,7,9,10,14,17}, and otherwise D = ∅. Hence the number of β-images is Bⁿ₃ = 2ⁿ − n − m, where m = 1 if n ∈ {5,7,9,10,14,17} and m = 0 otherwise.

Keywords: combinatorics on words, border correlation, square-free, cyclically square-free, Currie set

Full paper: [ps - 250 KB] [ps.gz - 119 KB] [pdf - 141 KB].