Density of critical factorizations

@article{Harju2002,
abstract = {We investigate the density of critical factorizations of infinite 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. 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. 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. 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.},
author = {Harju, Tero, Nowotka, Dirk},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {combinatorics on words; repetitions; critical factorization theorem; density of critical factorizations; Fibonacci words; Thue–Morse words; infinite sequences of words; critical factorization},
language = {eng},
number = {3},
pages = {315-327},
publisher = {EDP-Sciences},
title = {Density of critical factorizations},
url = {http://eudml.org/doc/245790},
volume = {36},
year = {2002},
}

TY - JOUR
AU - Harju, Tero
AU - Nowotka, Dirk
TI - Density of critical factorizations
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2002
PB - EDP-Sciences
VL - 36
IS - 3
SP - 315
EP - 327
AB - We investigate the density of critical factorizations of infinite 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. 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. 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. 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.
LA - eng
KW - combinatorics on words; repetitions; critical factorization theorem; density of critical factorizations; Fibonacci words; Thue–Morse words; infinite sequences of words; critical factorization
UR - http://eudml.org/doc/245790
ER -