Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > On the Density of Critical Fac...

On the Density of Critical Factorizations

Tero Harju, Dirk Nowotka, On the Density of Critical Factorizations. TUCS Technical Reports 435, Turku Centre for Computer Science, 2001.

Abstract:

<p>We investigate the density of critical positions, that is,
the ratio between the number of critical positions and
the number of all positions of a word, in infinite
sequences of words of index one, that is, the period
of which is longer than half of the length of the word.

<p>On one hand, we considered words with the lowest possible
number of critical points, namely one, and show, as
an example, that every Fibonacci word longer than five
has exactly one critical factorization which provides
a new way to prove two known facts about the periodicity
of Fibonacci words.

<p>On the other hand, sequences of words with a high density
of critical points are considered. We show how to construct
an infinite sequence of words in four letters where every
point in every word is critical. We construct an infinite
sequence of words in three letters with densities of
critical points approaching one, using square-free words,
and an infinite sequence of words in two letters with
densities of critical points approaching two, using
Thue-Morse words. It is shown that these bounds are
optimal.

<p>Furthermore, we give a short proof of the Critical
Factorization Theorem and a theorem about the maximal
distance between two critical points in a word. We state
that only words in a binary alphabet can have just one
critical factorization.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaNo01b,
  title = {On the Density of Critical Factorizations},
  author = {Harju, Tero and Nowotka, Dirk},
  number = {435},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2001},
  keywords = {combinatorics on words, repetitions, critical factorization theorem,
density of critical factorizations, Fibonacci words, Thue-Morse words},
  ISBN = {952-12-0937-2},
}

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

Edit publication