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

RAIRO - Theoretical Informatics and Applications (2010)

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

## Access Full Article

top## Abstract

top## How to cite

topWlazinski, 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- 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.
- J. Berstel, Axel thue's papers on repetitions in words: A translation, Technical Report 20. LaCIM, University of Québec at Montréal (1995).
- J. Berstel and P. Séébold, A characterization of overlap-free morphisms. Discrete Appl. Math.46 (1993) 275-281. Zbl0824.68093
- M. Crochemore, Sharp characterizations of squarefree morphisms. Theoret. Comput. Sci.18 (1982) 221-226. Zbl0482.68085
- J. Karhumäki, On cube free ω-words generated by binary morphisms. Discrete Appl. Math.5 (1983) 279-297. Zbl0505.03022
- 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
- V. Keränen, On the k-freeness of morphisms on free monoids. Ann. Acad. Sci. Fenn. 61 (1986). Zbl0604.20056
- M. Leconte, A characterization of power-free morphisms. Theoret. Comput. Sci.38 (1985) 117-122. Zbl0572.68066
- M. Leconte, Codes sans répétition, Ph.D. Thesis. LITP Université P. et M. Curie (1985). Zbl0571.68054
- 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
- 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
- M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (to appear). Zbl1001.68093
- V. Mitrana, Primitive morphisms. Inform. Process. Lett.64 (1997) 277-281. Zbl06590647
- M. Morse, Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc.22 (1921) 84-100. Zbl48.0786.06
- G. Richomme and P. Séébold, Characterization of test-sets for overlap-free morphisms. Discrete Appl. Math.98 (1999) 151-157. Zbl0946.68114
- 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
- G. Richomme and F. Wlazinski, Some results on k-power-free morphisms. Theoret. Comput. Sci.273 (2002) 119-142. Zbl1014.68127
- P. Séébold, Sequences generated by infinitely iterated morphisms. Discrete Appl. Math.11 (1985) 255-264. Zbl0583.20047
- A. Thue, Uber unendliche Zeichenreihen. Videnskapsselskapets Skrifter, I. Mat.-naturv. Klasse, Kristiania (1906) 1-22.
- A. Thue, Uber die gegenseitige Lage gleigher Teile gewisser Zeichenreihen. Videnskapsselskapets Skrifter, I. Mat.-naturv. Klasse, Kristiania (1912) 1-67. Zbl44.0462.01

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.