On critical exponents in fixed points of $k$-uniform binary morphisms

Krieger, Dalia

doi:10.1051/ita:2007042

On critical exponents in fixed points of

k

-uniform binary morphisms

Krieger, Dalia

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 1, pp. 41-68.

Résumé

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.

MR Zbl

DOI : 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},
     mrnumber = {2483444},
     zbl = {1170.68034},
     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
SP  - 41
EP  - 68
VL  - 43
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007042/
DO  - 10.1051/ita:2007042
LA  - en
ID  - ITA_2009__43_1_41_0
ER  -

%0 Journal Article
%A Krieger, Dalia
%T On critical exponents in fixed points of $k$-uniform binary morphisms
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2009
%P 41-68
%V 43
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2007042/
%R 10.1051/ita:2007042
%G en
%F ITA_2009__43_1_41_0

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/

Bibliographie
Cité par

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

[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 | Zbl

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

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

[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

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

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

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

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

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

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

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

[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 | Zbl

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

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

[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 | Zbl

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

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

[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

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

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

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

Cité par Sources :