A test-set for k-power-free binary morphisms

F. Wlazinski

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 35, Issue: 5, page 437-452
  • ISSN: 0988-3754

Abstract

top
A morphism f is k-power-free if and only if f(w) is k-power-free whenever w is a k-power-free word. A morphism f is k-power-free up to m if and only if f(w) is k-power-free whenever w is a k-power-free word of length at most m. Given an integer k ≥ 2, we prove that a binary morphism is k-power-free if and only if it is k-power-free up to k2. This bound becomes linear for primitive morphisms: a binary primitive morphism is k-power-free if and only if it is k-power-free up to 2k+1

How to cite

top

Wlazinski, F.. "A test-set for k-power-free binary morphisms." RAIRO - Theoretical Informatics and Applications 35.5 (2010): 437-452. <http://eudml.org/doc/222091>.

@article{Wlazinski2010,
abstract = { A morphism f is k-power-free if and only if f(w) is k-power-free whenever w is a k-power-free word. A morphism f is k-power-free up to m if and only if f(w) is k-power-free whenever w is a k-power-free word of length at most m. Given an integer k ≥ 2, we prove that a binary morphism is k-power-free if and only if it is k-power-free up to k2. This bound becomes linear for primitive morphisms: a binary primitive morphism is k-power-free if and only if it is k-power-free up to 2k+1},
author = {Wlazinski, F.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Combinatorics on words; k-power-free words; morphisms; test-sets; binary morphism},
language = {eng},
month = {3},
number = {5},
pages = {437-452},
publisher = {EDP Sciences},
title = {A test-set for k-power-free binary morphisms},
url = {http://eudml.org/doc/222091},
volume = {35},
year = {2010},
}

TY - JOUR
AU - Wlazinski, F.
TI - A test-set for k-power-free binary morphisms
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 35
IS - 5
SP - 437
EP - 452
AB - A morphism f is k-power-free if and only if f(w) is k-power-free whenever w is a k-power-free word. A morphism f is k-power-free up to m if and only if f(w) is k-power-free whenever w is a k-power-free word of length at most m. Given an integer k ≥ 2, we prove that a binary morphism is k-power-free if and only if it is k-power-free up to k2. This bound becomes linear for primitive morphisms: a binary primitive morphism is k-power-free if and only if it is k-power-free up to 2k+1
LA - eng
KW - Combinatorics on words; k-power-free words; morphisms; test-sets; binary morphism
UR - http://eudml.org/doc/222091
ER -

References

top
  1. J. Berstel, Axel thue's work on repetitions in words, edited by P. Leroux and C. Reutenauer, Séries formelles et combinatoire algébrique. LaCIM, University of Québec at Montréal (1992) 65-80.  
  2. J. Berstel, Axel thue's papers on repetitions in words: A translation, Technical Report 20. LaCIM, University of Québec at Montréal (1995).  
  3. J. Berstel and P. Séébold, A characterization of overlap-free morphisms. Discrete Appl. Math.46 (1993) 275-281.  
  4. M. Crochemore, Sharp characterizations of squarefree morphisms. Theoret. Comput. Sci.18 (1982) 221-226.  
  5. J. Karhumäki, On cube free ω-words generated by binary morphisms. Discrete Appl. Math.5 (1983) 279-297.  
  6. V. Keränen, On the k-repetition freeness of length uniform morphisms over a binary alphabet. Discrete Appl. Math.9 (1984) 297-300.  
  7. V. Keränen, On the k-freeness of morphisms on free monoids. Ann. Acad. Sci. Fenn. 61 (1986).  
  8. M. Leconte, A characterization of power-free morphisms. Theoret. Comput. Sci.38 (1985) 117-122.  
  9. M. Leconte, Codes sans répétition, Ph.D. Thesis. LITP Université P. et M. Curie (1985).  
  10. A. Lentin and M.P. Schützenberger, A combinatorial problem in the theory of free monoids, edited by R.C. Bose and T.E. Dowling. Chapell Hill, North Carolina Press edition, Comb. Math. (1945) 112-144.  
  11. M. Lothaire, Combinatorics on words, Vol. 17 of Encyclopedia of Mathematics, Chap. 9, Equations on words. Addison-Wesley (1983). Reprinted in 1997 by Cambridge University Press in the Cambridge Mathematical Library.  
  12. M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (to appear).  
  13. V. Mitrana, Primitive morphisms. Inform. Process. Lett.64 (1997) 277-281.  
  14. M. Morse, Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc.22 (1921) 84-100.  
  15. G. Richomme and P. Séébold, Characterization of test-sets for overlap-free morphisms. Discrete Appl. Math.98 (1999) 151-157.  
  16. G. Richomme and F. Wlazinski, About cube-free morphisms, edited by H. Reichel and S. Tison, STACS 2000. Springer-Verlag, Lecture Notes in Comput. Sci. 1770 (2000) 99-109.  
  17. G. Richomme and F. Wlazinski, Some results on k-power-free morphisms. Theoret. Comput. Sci.273 (2002) 119-142.  
  18. P. Séébold, Sequences generated by infinitely iterated morphisms. Discrete Appl. Math.11 (1985) 255-264.  
  19. A. Thue, Uber unendliche Zeichenreihen. Videnskapsselskapets Skrifter, I. Mat.-naturv. Klasse, Kristiania (1906) 1-22.  
  20. A. Thue, Uber die gegenseitige Lage gleigher Teile gewisser Zeichenreihen. Videnskapsselskapets Skrifter, I. Mat.-naturv. Klasse, Kristiania (1912) 1-67.  

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.