• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Border Correlation of Binary Words

Tero Harju, Dirk Nowotka, Border Correlation of Binary Words. TUCS Technical Reports 546, Turku Centre for Computer Science, 2003.

Abstract:

The border correlation function
&#946; : <i>A</i>^* &#8594; <i>A</i><sup>*</
sup>,
for <i>A</i> = {<i>a</i>, <i>b</i>}, specifies
which conjugates (cyclic shifts)
of a given word <i>w</i> of length <i>n</i> are bordered, i.e.,
&#946;(<i>w</i>) = <i>b</i>₀<i>b</i><sub>1</
sub>...<i>b</i>_<i>n</i>-1,
where <i>b</i>_<i>i</i> = <i>a</i>
or <i>b</i>
according to whether the <i>i</i>-th cyclic shift
&#963;^<i>i</i>(<i>w</i>)
of <i>w</i> is unbordered or bordered.
Except for some special cases, no binary word <i>w</i>
has two consecutive unbordered conjugates (&#963;^<i>i</i>(<i>w</i>)
and &#963;^<i>i</i>+1(<i>w</i>)).
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 &#946;. We prove that,
for each word <i>w</i> of length <i>n</i>, the sequence
<i>w</i>, &#946;(<i>w</i>), &#946;²(<i>w</i>), ...
terminates either in <i>b</i>^<i>n</i> or
in the cycle of conjugates of the word
<i>ab</i>^<i>k</i><i>ab</i>^<i>k</i>+1
for <i>n</i> = 2<i>k</i>+3.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaD03a,
  title = {Border Correlation of Binary Words},
  author = {Harju, Tero and Nowotka, Dirk},
  number = {546},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2003},
  keywords = {combinatorics on words, border correlation, binary words},
  ISBN = {952-12-1205-5},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication