A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Border correlation of binary words
Tekijät: Harju T, Nowotka D
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2004
Lehti:: Journal of Combinatorial Theory, Series A
Tietokannassa oleva lehden nimi: JOURNAL OF COMBINATORIAL THEORY SERIES A
Lehden akronyymi: J COMB THEORY A
Vuosikerta: 108
Numero: 2
Aloitussivu: 331
Lopetussivu: 341
Sivujen määrä: 11
ISSN: 0097-3165
DOI: https://doi.org/10.1016/j.jcta.2004.07.009
Tiivistelmä
The border correlation function beta: A* --> A*, for A = {a, b}, specifies which conjugates (cyclic shifts) of a given word w of length n are bordered, in other words, beta(w) = c(0)c(1)... c(n- 1), where c(i) = a or b according to whether the ith cyclic shift sigma(i)(w) of w is unbordered orbordered. Except for some special cases, no binary word w has two consecutive unbordered conjugates (sigma(i)(w) and sigma(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 beta. We prove that, for each word w of length n, the sequence w, beta(w), beta(2)(w),... terminates either in b(n) or in the cycle of conjugates of the word ab(k)ab(k+l) for n = 2k + 3. (C) 2004 Elsevier Inc. All rights reserved.
The border correlation function beta: A* --> A*, for A = {a, b}, specifies which conjugates (cyclic shifts) of a given word w of length n are bordered, in other words, beta(w) = c(0)c(1)... c(n- 1), where c(i) = a or b according to whether the ith cyclic shift sigma(i)(w) of w is unbordered orbordered. Except for some special cases, no binary word w has two consecutive unbordered conjugates (sigma(i)(w) and sigma(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 beta. We prove that, for each word w of length n, the sequence w, beta(w), beta(2)(w),... terminates either in b(n) or in the cycle of conjugates of the word ab(k)ab(k+l) for n = 2k + 3. (C) 2004 Elsevier Inc. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali