Density of Critical Factorizations

Tero Harju; Dirk Nowotka

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 36, Issue: 3, page 315-327
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Harju, Tero, and Nowotka, Dirk. "Density of Critical Factorizations." RAIRO - Theoretical Informatics and Applications 36.3 (2010): 315-327. <http://eudml.org/doc/92704>.

@article{Harju2010,
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},
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},
month = {3},
number = {3},
pages = {315-327},
publisher = {EDP Sciences},
title = {Density of Critical Factorizations},
url = {http://eudml.org/doc/92704},
volume = {36},
year = {2010},
}

TY - JOUR
AU - Harju, Tero
AU - Nowotka, Dirk
TI - Density of Critical Factorizations
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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/92704
ER -

References

top
  1. J. Berstel, Axel Thue's work on repetitions in words, edited by P. Leroux and Ch. Reutenauer, Séries formelles et combinatoire algébrique. Université du Québec à Montréal, Publications du LaCIM 11 (1992) 65-80.  
  2. J. Berstel, Axel Thue's papers on repetitions in words: A translation. Université du Québec à Montréal, Publications du LaCIM 20 (1995).  
  3. Y. Césari and M. Vincent, Une caractérisation des mots périodiques. C. R. Hebdo. Séances Acad. Sci. 286(A) (1978) 1175-1177.  Zbl0392.20039
  4. Ch. Choffrut and J. Karhumäki, Combinatorics of words, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin, Handb. Formal Languages 1 (1997) 329-438.  
  5. M. Crochemore and D. Perrin, Two-way string-matching. J. ACM38 (1991) 651-675.  Zbl0808.68063
  6. A. de Luca, A combinatorial property of the Fibonacci words. Inform. Process. Lett.12 (1981) 193-195.  Zbl0468.20049
  7. J.-P. Duval, Périodes et répétitions des mots de monoïde libre. Theoret. Comput. Sci.9 (1979) 17-26.  Zbl0402.68052
  8. M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, Massachusetts, Encyclopedia of Math. 17 (1983).  Zbl0514.20045
  9. M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, United Kingdom (2002).  Zbl1001.68093
  10. M. Morse, Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc.22 (1921) 84-100.  Zbl48.0786.06
  11. A. Thue, Über unendliche Zeichenreihen. Det Kongelige Norske Videnskabersselskabs Skrifter, I Mat.-nat. Kl. Christiania 7 (1906) 1-22.  
  12. A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Det Kongelige Norske Videnskabersselskabs Skrifter, I Mat.-nat. Kl. Christiania 1 (1912) 1-67.  Zbl44.0462.01

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.