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

F. Wlazinski

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

  • 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 k 2 . 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 2 k + 1

How to cite

top

Wlazinski, F.. "A test-set for $k$-power-free binary morphisms." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.5 (2001): 437-452. <http://eudml.org/doc/92676>.

@article{Wlazinski2001,
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 \ge 2$, we prove that a binary morphism is $k$-power-free if and only if it is $k$-power-free up to $k^2$. 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 - Informatique Théorique et Applications},
keywords = {combinatorics on words; $k$-power-free words; morphisms; test-sets; binary morphism},
language = {eng},
number = {5},
pages = {437-452},
publisher = {EDP-Sciences},
title = {A test-set for $k$-power-free binary morphisms},
url = {http://eudml.org/doc/92676},
volume = {35},
year = {2001},
}

TY - JOUR
AU - Wlazinski, F.
TI - A test-set for $k$-power-free binary morphisms
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2001
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 \ge 2$, we prove that a binary morphism is $k$-power-free if and only if it is $k$-power-free up to $k^2$. 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/92676
ER -

References

top
  1. [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. [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. [3] J. Berstel and P. Séébold, A characterization of overlap-free morphisms. Discrete Appl. Math. 46 (1993) 275-281. Zbl0824.68093MR1243728
  4. [4] M. Crochemore, Sharp characterizations of squarefree morphisms. Theoret. Comput. Sci. 18 (1982) 221-226. Zbl0482.68085MR652471
  5. [5] J. Karhumäki, On cube free ω -words generated by binary morphisms. Discrete Appl. Math. 5 (1983) 279-297. Zbl0505.03022MR690339
  6. [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.68082MR763566
  7. [7] V. Keränen, On the k -freeness of morphisms on free monoids. Ann. Acad. Sci. Fenn. 61 (1986). Zbl0604.20056MR869270
  8. [8] M. Leconte, A characterization of power-free morphisms. Theoret. Comput. Sci. 38 (1985) 117-122. Zbl0572.68066MR805137
  9. [9] M. Leconte, Codes sans répétition, Ph.D. Thesis. LITP Université P. et M. Curie (1985). 
  10. [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. [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. [12] M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (to appear). Zbl1001.68093MR1905123
  13. [13] V. Mitrana, Primitive morphisms. Inform. Process. Lett. 64 (1997) 277-281. Zbl06590647MR1608236
  14. [14] M. Morse, Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc. 22 (1921) 84-100. Zbl48.0786.06MR1501161JFM48.0786.06
  15. [15] G. Richomme and P. Séébold, Characterization of test-sets for overlap-free morphisms. Discrete Appl. Math. 98 (1999) 151-157. Zbl0946.68114MR1723693
  16. [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.68532MR1781724
  17. [17] G. Richomme and F. Wlazinski, Some results on k -power-free morphisms. Theoret. Comput. Sci. 273 (2002) 119-142. Zbl1014.68127MR1872446
  18. [18] P. Séébold, Sequences generated by infinitely iterated morphisms. Discrete Appl. Math. 11 (1985) 255-264. Zbl0583.20047MR792893
  19. [19] A. Thue, Uber unendliche Zeichenreihen. Videnskapsselskapets Skrifter, I. Mat.-naturv. Klasse, Kristiania (1906) 1-22. Zbl39.0283.01JFM39.0283.01
  20. [20] A. Thue, Uber die gegenseitige Lage gleigher Teile gewisser Zeichenreihen. Videnskapsselskapets Skrifter, I. Mat.-naturv. Klasse, Kristiania (1912) 1-67. Zbl44.0462.01JFM44.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.