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

Dalia Krieger

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2009)

  • Volume: 43, Issue: 1, page 41-68
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Krieger, Dalia. "On critical exponents in fixed points of $k$-uniform binary morphisms." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 43.1 (2009): 41-68. <http://eudml.org/doc/244935>.

@article{Krieger2009,
abstract = {Let $\mathbf \{w\}$ be an infinite fixed point of a binary $k$-uniform morphism $f$, and let $E(\mathbf \{w\})$ be the critical exponent of $\mathbf \{w\}$. We give necessary and sufficient conditions for $E(\mathbf \{w\})$ to be bounded, and an explicit formula to compute it when it is. In particular, we show that $E(\mathbf \{w\})$ is always rational. We also sketch an extension of our method to non-uniform morphisms over general alphabets.},
author = {Krieger, Dalia},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {critical exponent; binary $k$-uniform morphism; binary -uniform morphism},
language = {eng},
number = {1},
pages = {41-68},
publisher = {EDP-Sciences},
title = {On critical exponents in fixed points of $k$-uniform binary morphisms},
url = {http://eudml.org/doc/244935},
volume = {43},
year = {2009},
}

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
PB - EDP-Sciences
VL - 43
IS - 1
SP - 41
EP - 68
AB - Let $\mathbf {w}$ be an infinite fixed point of a binary $k$-uniform morphism $f$, and let $E(\mathbf {w})$ be the critical exponent of $\mathbf {w}$. We give necessary and sufficient conditions for $E(\mathbf {w})$ to be bounded, and an explicit formula to compute it when it is. In particular, we show that $E(\mathbf {w})$ is always rational. We also sketch an extension of our method to non-uniform morphisms over general alphabets.
LA - eng
KW - critical exponent; binary $k$-uniform morphism; binary -uniform morphism
UR - http://eudml.org/doc/244935
ER -

References

top
  1. [1] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). Zbl1086.11015MR1997038
  2. [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. [3] J. Berstel, On the Index of Sturmian Words, in Jewels are forever. Springer, Berlin (1999) 287–294. Zbl0982.11010MR1719097
  4. [4] W.-T. Cao and Z.-Y. Wen, Some properties of the factors of Sturmian sequences. Theoret. Comput. Sci. 304 (2003) 365–385. Zbl1045.68109MR1992341
  5. [5] A. Carpi and A. de Luca, Special factors, periodicity, and an application to Sturmian words. Acta Informatica 36 (2000) 983–1006. Zbl0956.68119MR1776146
  6. [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. MR1318456
  7. [7] D. Damanik and D. Lenz, The index of Sturmian sequences. Eur. J. Combin. 23 (2002) 23–29. Zbl1002.11020MR1878771
  8. [8] A. Ehrenfeucht and G. Rozenberg, Repetition of subwords in D0L languages. Inform. Control 59 (1983) 13–35. Zbl0549.68076MR760154
  9. [9] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109–114. Zbl0131.30203MR174934
  10. [10] A.E. Frid, On uniform DOL words. STACS’98 1373 (1998) 544–554. MR1650675
  11. [11] J. Justin and G. Pirillo, Fractional powers in Sturmian words. Theoret. Comput. Sci. 255 (2001) 363–376. Zbl0974.68159MR1819081
  12. [12] A.V. Klepinin and E.V. Sukhanov, On combinatorial properties of the Arshon sequence. Discrete Appl. Math. 114 (2001) 155–169. Zbl0995.68506MR1865589
  13. [13] Y. Kobayashi and F. Otto, Repetitiveness of languages generated by morphisms. Theoret. Comput. Sci. 240 (2000) 337–378. Zbl0947.68086MR1776378
  14. [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. Zbl1137.68047MR2249361
  15. [15] D. Krieger, On critical exponents in fixed points of non-erasing morphisms. Theoret. Comput. Sci. 376 (2007) 70–88. Zbl1111.68058MR2316392
  16. [16] M. Lothaire, Algebraic Combinatorics on Words, Vol. 90 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press (2002). Zbl1001.68093MR1905123
  17. [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. Zbl0106.02204MR162838
  18. [18] F. Mignosi, Infinite words with linear subword complexity. Theoret. Comput. Sci. 65 (1989) 221–242. Zbl0682.68083MR1020489
  19. [19] F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl. 26 (1992) 199–204. Zbl0761.68078MR1170322
  20. [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. 
  21. [21] B. Mossé, Puissances de mots et reconnaissabilité des points fixes d’une substitution. Theoret. Comput. Sci. 99 (1992) 327–334. Zbl0763.68049MR1168468
  22. [22] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1–67. Zbl44.0462.01JFM44.0462.01
  23. [23] D. Vandeth, Sturmian Words and Words with Critical Exponent. Theoret. Comput. Sci. 242 (2000) 283–300. Zbl0944.68148MR1769782

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.