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.  Zbl0824.68093
  4. M. Crochemore, Sharp characterizations of squarefree morphisms. Theoret. Comput. Sci.18 (1982) 221-226.  Zbl0482.68085
  5. J. Karhumäki, On cube free ω-words generated by binary morphisms. Discrete Appl. Math.5 (1983) 279-297.  Zbl0505.03022
  6. V. Keränen, On the k-repetition freeness of length uniform morphisms over a binary alphabet. Discrete Appl. Math.9 (1984) 297-300.  Zbl0547.68082
  7. V. Keränen, On the k-freeness of morphisms on free monoids. Ann. Acad. Sci. Fenn. 61 (1986).  Zbl0604.20056
  8. M. Leconte, A characterization of power-free morphisms. Theoret. Comput. Sci.38 (1985) 117-122.  Zbl0572.68066
  9. M. Leconte, Codes sans répétition, Ph.D. Thesis. LITP Université P. et M. Curie (1985).  Zbl0571.68054
  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.  Zbl0221.20076
  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.  Zbl0514.20045
  12. M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (to appear).  Zbl1001.68093
  13. V. Mitrana, Primitive morphisms. Inform. Process. Lett.64 (1997) 277-281.  Zbl06590647
  14. M. Morse, Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc.22 (1921) 84-100.  Zbl48.0786.06
  15. G. Richomme and P. Séébold, Characterization of test-sets for overlap-free morphisms. Discrete Appl. Math.98 (1999) 151-157.  Zbl0946.68114
  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.  Zbl0959.68532
  17. G. Richomme and F. Wlazinski, Some results on k-power-free morphisms. Theoret. Comput. Sci.273 (2002) 119-142.  Zbl1014.68127
  18. P. Séébold, Sequences generated by infinitely iterated morphisms. Discrete Appl. Math.11 (1985) 255-264.  Zbl0583.20047
  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.  Zbl44.0462.01

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.