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

A Characterization of the Periodicity of Bi-Infinite Words

Tero Harju, Arto Lepistö, Dirk Nowotka, A Characterization of the Periodicity of Bi-Infinite Words. TUCS Technical Reports 545, Turku Centre for Computer Science, 2003.

Abstract:

A finite word is called bordered if it has a proper prefix
which is also a suffix of that word. Costa proves
in [Theoret. Comput. Sci., 290(3):2053-2061, 2003]
that a bi-infinite word <i>w</i> is of the form
<i>^&#969;fgf^&#969;</i>,
for some finite words <i>f</i> and <i>g</i>, if, and only if,
there is a factorization <i>w</i> = <i>suv</i>,
where <i>u</i> is a finite word and every factor
<i>s'uv'</i>, where <i>s'</i> is a suffix of <i>s</i>
and <i>v'</i> is a prefix of <i>v</i>, is bordered.
We present a shorter proof of that result in this paper.

Files:

Abstract in PDF-format

BibTeX entry:

@TECHREPORT{tHaA03a,
  title = {A Characterization of the Periodicity of Bi-Infinite Words},
  author = {Harju, Tero and Lepistö, Arto and Nowotka, Dirk},
  number = {545},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2003},
  keywords = {combinatorics on words, bi-infinite words, unbordered factors, periodicity},
  ISBN = {952-12-1204-7},
}

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

Edit publication