Tero Harju and Dirk Nowotka Border Correlation of Binary Words Journal of Combinatorial Theory, Series A, 108(2):331-341, 2004. AbstractThe border correlation function β : A^{*} → A^{*}, for A = {a, b}, specifies which conjugates (cyclic shifts) of a given word w of length n are bordered, i.e., β(w) = b_{0}b_{1}...b_{n-1}, where b_{i} = a or b according to whether the i-th cyclic shift σ^{i}(w) of w is unbordered or bordered. Except for some special cases, no binary word w has two consecutive unbordered conjugates (σ^{i}(w) and σ^{i+1}(w)). We show that this is optimal: in every cyclically overlap-free word every other conjugate is unbordered. We also study the relationship between unbordered conjugates and critical points, as well as, the dynamic system given by iterating the function β. We prove that, for each word w of length n, the sequence w, β(w), β^{2}(w), ... terminates either in b^{n} or in the cycle of conjugates of the word ab^{k}ab^{k+1} for n = 2k+3. Keywords: combinatorics on words, border correlation, binary words Full paper: [ps - 808 KB] [ps.gz - 124 KB] [pdf - 150 KB]. |