Bordered Conjugates of Words over Large Alphabets

: Harju T, Nowotka D

Publisher: ELECTRONIC JOURNAL OF COMBINATORICS

: 2008

The Electronic Journal of Combinatorics

ELECTRONIC JOURNAL OF COMBINATORICS

: ELECTRON J COMB

: ARTN N41

: 15

: 1

: 7

: 1077-8926

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

Mathematics