Length-k-overlap-free Binary Infinite Words

• Autorzy: Séébold P.
• Języki publikacji: EN

Abstrakty

EN

We study length-k-overlap-free binary infinite words, i.e., binary infinite words which can contain only overlaps xyxyx with |x| ≤ k-1. We prove that no such word can be generated by a morphism, except if k = 1. On the other hand, for every k ≥ 2, there exist length-k-overlap-free binary infinite words which are not length-(k-1)-overlap-free. As an application, we prove that, for every non-negative integer n, there exist infinitely many length-k-overlap-free binary infinite partial words with n holes.

Słowa kluczowe

EN

repetition-freeness; length-k-overlaps; partial words; Thue-Morse word; infinite words

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 251--263
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Séébold P.

• Univ. Montpellier 3 Paul Valéry, Montpellier, F-34199, France LIRMM, CNRS, F-34392, France,

Bibliografia

• [1] J.-P. ALLOUCHE, J. SHALLIT, The ubiquitous Prouhet-Thue-Morse sequence, in: C. Ding. T. Helleseth, H. Niederreiter (Eds.), Sequences and Their Applications, Proceedings of SETA'98, Springer-Verlag (1999), 1-16.
• [2] J. BERSTEL, Axel Thue's work on repetitions in words, in: Leroux, Reutenauer (eds), Séries formelles et combinatoire algébrique, Publications du LaCIM, Université du Québec a Montréal,Montréal (1992) 65-80. See also Axel Thue's papers on repetitions in words: a translation, Publications du LaCIM, Département de mathématiques et d'informatique, Université du Québec `a Montréal 20 (1995), 85 pages.
• [3] J. BERSTEL, L. BOASSON, Partial words and a theorem of Fine andWilf, Theoret. Comput. Sci. 218 (1999), 135-141.
• [4] F. BLANCHET-SADRI, Algorithmic Combinatorics on Partial Words, Chapman & Hall/CRC Press, Boca Raton, FL, 2007.
• [5] J. BERSTEL, P. Séé BOLD, A characterization of overlap-free morphisms, Discrete Appl. Math. 46 (1993), 275-281.
• [6] V. HALAVA, T. HARJU, T. KäRKI, P. Séé BOLD, Overlap-freeness in infinite partial words, Theoret. Comput. Sci. 410 (2009), 943-948.
• [7] M. LOTHAIRE, Combinatorics on Words, vol. 17 of Encyclopedia of Mathematics and Applications, Addison-Wesley, Reading, Mass., 1983. Reprinted in the Cambridge Mathematical Library, Cambridge University Press, Cambridge, UK, 1997.
• [8] M. MORSE, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc. 22 (1921), 84-100.
• [9] N. RAMPERSAD, J. SHALLIT, M.-W. WANG, Avoiding large squares in infinite binary words, Theoret. Comput. Sci. 339 (2005), 19-34.
• [10] P. Séé BOLD, Sequences generated by infinitely iterated morphisms, Discrete Appl. Math. 11 (1985), 255-264.
• [11] P. Séé BOLD, k-overlap-free words, Preprint, JORCAD'08, Rouen, France (2008), 47-49.
• [12] J. SHALLIT, Simultaneous Avoidance Of Large Squares And Fractional Powers In Infinite Binary Words, Int. J. Found. Comput. Sci. 15 (2004), 317-327.
• [13] A. THUE, über unendliche Zeichenreihen, Christiania Vidensk.-Selsk. Skrifter. I. Mat. Nat. Kl. 7 (1906), 1-22.
• [14] A. THUE, über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen,Vidensk.-Selsk. Skrifter. I.Mat. Nat. Kl. 1 Kristiania (1912), 1-67.