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

Density of Critical Factorizations

Tero Harju, Dirk Nowotka, Density of Critical Factorizations. Theoretical Informatics and Applications 3(36), 315-327, 2002.

Abstract:

<P>We investigate the density of critical factorizations of infinte
sequences of words. The density of critical factorizations
of a word is the ratio between the number of positions
that permit a critical factorization, and the number of
all positions of a word.

<P>We give a short proof of the Critical Factorization Theorem
and show that the maximal number of noncritical positions
of a word between two critical ones is less than the period
of that word. Therefore, we consider only words of index one,
that is words where the shortest period is larger than one half
of their total length, in this paper.

<P>On one hand, we consider words with the lowest possible number
of critical points and show, as an example,
that every Fibonacci word longer than five has exactly one critical
factorization and every palindrome has at least two critical
factorizations.

<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 one half, using
Thue-Morse words. It is shown that these bounds are optimal.

Files:

Full publication in PDF-format

BibTeX entry:

@ARTICLE{jHaNo02a,
  title = {Density of Critical Factorizations},
  author = {Harju, Tero and Nowotka, Dirk},
  journal = {Theoretical Informatics and Applications},
  volume = {3},
  number = {36},
  pages = {315-327},
  year = {2002},
  keywords = {combinatorics on words, repetitions, critical factorization theorem, density of critical factorizations, Fibonacci words, Thue-Morse words},
}

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

Edit publication