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

Dalia Krieger

RAIRO - Theoretical Informatics and Applications (2007)

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

Abstract

top
Let w be an infinite fixed point of a binary k-uniform morphism f, and let Ew be the critical exponent of w. We give necessary and sufficient conditions for Ew to be bounded, and an explicit formula to compute it when it is. In particular, we show that Ew 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 43.1 (2007): 41-68. <http://eudml.org/doc/92907>.

@article{Krieger2007,
abstract = { Let w be an infinite fixed point of a binary k-uniform morphism f, and let Ew be the critical exponent of w. We give necessary and sufficient conditions for Ew to be bounded, and an explicit formula to compute it when it is. In particular, we show that Ew 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},
keywords = {Critical exponent; binary k-uniform morphism.; critical exponent; binary -uniform morphism},
language = {eng},
month = {12},
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/92907},
volume = {43},
year = {2007},
}

TY - JOUR
AU - Krieger, Dalia
TI - On Critical exponents in fixed points of k-uniform binary morphisms
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/12//
PB - EDP Sciences
VL - 43
IS - 1
SP - 41
EP - 68
AB - Let w be an infinite fixed point of a binary k-uniform morphism f, and let Ew be the critical exponent of w. We give necessary and sufficient conditions for Ew to be bounded, and an explicit formula to compute it when it is. In particular, we show that Ew 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.; critical exponent; binary -uniform morphism
UR - http://eudml.org/doc/92907
ER -

References

top
  1. J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003).  
  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.  
  4. W.-T. Cao and Z.-Y. Wen, Some properties of the factors of Sturmian sequences. Theoret. Comput. Sci.304 (2003) 365–385.  
  5. A. Carpi and A. de Luca, Special factors, periodicity, and an application to Sturmian words. Acta Informatica36 (2000) 983–1006.  
  6. J. Cassaigne, An algorithm to test if a given circular HD0L-language avoids a pattern, in IFIP World Computer Congress'941 (1994) 459–464.  
  7. D. Damanik and D. Lenz, The index of Sturmian sequences. Eur. J. Combin.23 (2002) 23–29.  
  8. A. Ehrenfeucht and G. Rozenberg, Repetition of subwords in D0L languages. Inform. Control59 (1983) 13–35.  
  9. N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc.16 (1965) 109–114.  
  10. A.E. Frid, On uniform DOL words. STACS'981373 (1998) 544–554.  
  11. J. Justin and G. Pirillo, Fractional powers in Sturmian words. Theoret. Comput. Sci.255 (2001) 363–376.  
  12. A.V. Klepinin and E.V. Sukhanov, On combinatorial properties of the Arshon sequence. Discrete Appl. Math.114 (2001) 155–169.  
  13. Y. Kobayashi and F. Otto, Repetitiveness of languages generated by morphisms. Theoret. Comput. Sci.240 (2000) 337–378.  
  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.  
  15. D. Krieger, On critical exponents in fixed points of non-erasing morphisms. Theoret. Comput. Sci.376 (2007) 70–88.  
  16. M. Lothaire, Algebraic Combinatorics on Words, Vol. 90 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press (2002).  
  17. R.C. Lyndon and M.P. Schützenberger, The equation aM = bNcP in a free group. Michigan Math. J.9 (1962) 289–298.  
  18. F. Mignosi, Infinite words with linear subword complexity. Theoret. Comput. Sci.65 (1989) 221–242.  
  19. F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl.26 (1992) 199–204.  
  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. B. Mossé, Puissances de mots et reconnaissabilité des points fixes d'une substitution. Theoret. Comput. Sci.99 (1992) 327–334.  
  22. A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl.1 (1912) 1–67.  
  23. D. Vandeth, Sturmian Words and Words with Critical Exponent. Theoret. Comput. Sci.242 (2000) 283–300.  

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.