Density of Critical Factorizations

Issue		RAIRO-Theor. Inf. Appl. Volume 36, Number 3, July-September 2002


Page(s)		315 - 327
DOI		10.1051/ita:2002016

Theoret. Informatics Appl. 36, 315-327 (2002)
DOI: 10.1051/ita:2002016

Tero Harju and Dirk Nowotka

Turku Centre for Computer Science, TUCS, and Department of Mathematics, University of Turku; harju@utu.fi. nowotka@utu.fi.

(Received April, 2002. Accepted October, 2002.)

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.

Mathematics Subject Classification. 68R15

Key words: Combinatorics on words -- repetitions -- Critical Factorization Theorem -- density of critical factorizations -- Fibonacci words -- Thue-Morse words.

© EDP Sciences 2002

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.