On critical exponents in fixed points of k-uniform binary morphisms
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 1, pp. 41-68.

Let 𝐰 be an infinite fixed point of a binary k-uniform morphism f, and let E(𝐰) be the critical exponent of 𝐰. We give necessary and sufficient conditions for E(𝐰) to be bounded, and an explicit formula to compute it when it is. In particular, we show that E(𝐰) is always rational. We also sketch an extension of our method to non-uniform morphisms over general alphabets.

DOI : https://doi.org/10.1051/ita:2007042
Classification : 68R15
Mots clés : critical exponent, binary k-uniform morphism
@article{ITA_2009__43_1_41_0,
     author = {Krieger, Dalia},
     title = {On critical exponents in fixed points of $k$-uniform binary morphisms},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {41--68},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {1},
     year = {2009},
     doi = {10.1051/ita:2007042},
     zbl = {1170.68034},
     mrnumber = {2483444},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2007042/}
}
TY  - JOUR
AU  - Krieger, Dalia
TI  - On critical exponents in fixed points of $k$-uniform binary morphisms
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2009
DA  - 2009///
SP  - 41
EP  - 68
VL  - 43
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007042/
UR  - https://zbmath.org/?q=an%3A1170.68034
UR  - https://www.ams.org/mathscinet-getitem?mr=2483444
UR  - https://doi.org/10.1051/ita:2007042
DO  - 10.1051/ita:2007042
LA  - en
ID  - ITA_2009__43_1_41_0
ER  - 
Krieger, Dalia. On critical exponents in fixed points of $k$-uniform binary morphisms. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 1, pp. 41-68. doi : 10.1051/ita:2007042. http://www.numdam.org/articles/10.1051/ita:2007042/

[1] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). | MR 1997038 | Zbl 1086.11015

[2] J. Berstel, Axel Thue's Papers on Repetitions in Words: A Translation. Publications du Laboratoire de Combinatoire et d'Informatique Mathématique 20, Université du Québec à Montréal (1995).

[3] J. Berstel, On the Index of Sturmian Words, in Jewels are forever. Springer, Berlin (1999) 287-294. | MR 1719097 | Zbl 0982.11010

[4] W.-T. Cao and Z.-Y. Wen, Some properties of the factors of Sturmian sequences. Theoret. Comput. Sci. 304 (2003) 365-385. | MR 1992341 | Zbl 1045.68109

[5] A. Carpi and A. De Luca, Special factors, periodicity, and an application to Sturmian words. Acta Informatica 36 (2000) 983-1006. | MR 1776146 | Zbl 0956.68119

[6] J. Cassaigne, An algorithm to test if a given circular HD0L-language avoids a pattern, in IFIP World Computer Congress'94 1 (1994) 459-464. | MR 1318456

[7] D. Damanik and D. Lenz, The index of Sturmian sequences. Eur. J. Combin. 23 (2002) 23-29. | MR 1878771 | Zbl 1002.11020

[8] A. Ehrenfeucht and G. Rozenberg, Repetition of subwords in D0L languages. Inform. Control 59 (1983) 13-35. | MR 760154 | Zbl 0549.68076

[9] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. | MR 174934 | Zbl 0131.30203

[10] A.E. Frid, On uniform DOL words. STACS'98 1373 (1998) 544-554. | MR 1650675

[11] J. Justin and G. Pirillo, Fractional powers in Sturmian words. Theoret. Comput. Sci. 255 (2001) 363-376. | MR 1819081 | Zbl 0974.68159

[12] A.V. Klepinin and E.V. Sukhanov, On combinatorial properties of the Arshon sequence. Discrete Appl. Math. 114 (2001) 155-169. | MR 1865589 | Zbl 0995.68506

[13] Y. Kobayashi and F. Otto, Repetitiveness of languages generated by morphisms. Theoret. Comput. Sci. 240 (2000) 337-378. | MR 1776378 | Zbl 0947.68086

[14] D. Krieger, On critical exponents in fixed points of binary k-uniform morphisms, in STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, edited by B. Durand and W. Thomas. Lect. Notes. Comput. Sci. 3884 (2006) 104-114. | MR 2249361 | Zbl 1137.68047

[15] D. Krieger, On critical exponents in fixed points of non-erasing morphisms. Theoret. Comput. Sci. 376 (2007) 70-88. | MR 2316392 | Zbl 1111.68058

[16] M. Lothaire, Algebraic Combinatorics on Words, Vol. 90 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press (2002). | MR 1905123 | Zbl 1001.68093

[17] R.C. Lyndon and M.P. Schützenberger, The equation a M =b N c P in a free group. Michigan Math. J. 9 (1962) 289-298. | MR 162838 | Zbl 0106.02204

[18] F. Mignosi, Infinite words with linear subword complexity. Theoret. Comput. Sci. 65 (1989) 221-242. | MR 1020489 | Zbl 0682.68083

[19] F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl. 26 (1992) 199-204. | EuDML 92414 | Numdam | MR 1170322 | Zbl 0761.68078

[20] F. Mignosi and P. Séébold, If a D0L language is k-power free then it is circular. ICALP'93. Lect. Notes Comput. Sci. 700 (1993) 507-518. | MR 1252430

[21] B. Mossé, Puissances de mots et reconnaissabilité des points fixes d'une substitution. Theoret. Comput. Sci. 99 (1992) 327-334. | MR 1168468 | Zbl 0763.68049

[22] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1-67. | JFM 44.0462.01

[23] D. Vandeth, Sturmian Words and Words with Critical Exponent. Theoret. Comput. Sci. 242 (2000) 283-300. | MR 1769782 | Zbl 0944.68148

Cité par Sources :