Binary patterns in binary cube-free words: Avoidability and growth
Mercaş, Robert ; Ochem, Pascal ; Samsonov, Alexey V. ; Shur, Arseny M.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014), p. 369-389 / Harvested from Numdam
Access to full text

The avoidability of binary patterns by binary cube-free words is investigated and the exact bound between unavoidable and avoidable patterns is found. All avoidable patterns are shown to be D0L-avoidable. For avoidable patterns, the growth rates of the avoiding languages are studied. All such languages, except for the overlap-free language, are proved to have exponential growth. The exact growth rates of languages avoiding minimal avoidable patterns are approximated through computer-assisted upper bounds. Finally, a new example of a pattern-avoiding language of polynomial growth is given.

Publié le : 2014-01-01
DOI : https://doi.org/10.1051/ita/2014015
Classification:  68Q70,  68R15 
@article{ITA_2014__48_4_369_0,
     author = {Merca\c s, Robert and Ochem, Pascal and Samsonov, Alexey V. and Shur, Arseny M.},
     title = {Binary patterns in binary cube-free words: Avoidability and growth},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {48},
     year = {2014},
     pages = {369-389},
     doi = {10.1051/ita/2014015},
     mrnumber = {3302493},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2014__48_4_369_0}
}

Mercaş, Robert; Ochem, Pascal; Samsonov, Alexey V.; Shur, Arseny M. Binary patterns in binary cube-free words: Avoidability and growth. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) pp. 369-389. doi : 10.1051/ita/2014015. http://gdmltest.u-ga.fr/item/ITA_2014__48_4_369_0/

[1] Growth-rate-calculator. Library for calculating growth rates of factorial formal languages (2013). Available at http://code.google.com/p/growth-rate-calculator/.

[2] G. Badkobeh, S. Chairungsee and M. Crochemore, Hunting redundancies in strings. In Proc. 15th Developments in Language Theory. DLT 2011, Vol.6795 of Lect. Notes Sci. Springer, Berlin (2011) 1-14. | MR 2862710 | Zbl 1217.68164

[3] K.A. Baker, G.F. Mcnulty and W. Taylor, Growth problems for avoidable words. Theoret. Comput. Sci. 69 (1989) 319-345. | MR 1036470 | Zbl 0693.68039

[4] D.A. Bean, A. Ehrenfeucht and G. Mcnulty, Avoidable patterns in strings of symbols. Pacific J. Math. 85 (1979) 261-294. | MR 574919 | Zbl 0428.05001

[5] J.P. Bell and T.L. Goh, Exponential lower bounds for the number of words of uniform length avoiding a pattern. Inform. Comput. 205 (2007) 1295-1306. | MR 2334234 | Zbl 1127.68073

[6] V.D. Blondel, J. Cassaigne and R. Jungers, On the number of α-power-free binary words for 2 <α ≤ 7/3. Theoret. Comput. Sci. 410 (2009) 2823-2833. | MR 2543336 | Zbl 1173.68046

[7] F.-J. Brandenburg, Uniformly growing k-th power-free homomorphisms. Theoret. Comput. Sci. 23 (1983) 69-82. | MR 693069 | Zbl 0508.68051

[8] J. Cassaigne, Unavoidable binary patterns. Acta Informatica 30 (1993) 385-395. | MR 1227889 | Zbl 0790.68096

[9] J. Cassaigne, Motifs évitables et régularités dans les mots (Thèse de Doctorat). Tech. Report. LITP-TH 94-04 (1994).

[10] C. Choffrut and J. Karhumäki, Combinatorics of words. In vol. 1 of Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag (1997) 329-438. | MR 1469998 | Zbl 0866.68057

[11] P. Goralcik and T. Vanicek, Binary patterns in binary words. Internat. J. Algebra Comput. 1 (1991) 387-391. | MR 1148238 | Zbl 0759.68051

[12] J. Karhumäki and J. Shallit, Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory. Ser. A 104 (2004) 335-347. | MR 2046086 | Zbl 1065.68080

[13] P. Ochem, A generator of morphisms for infinite words. RAIRO: ITA 40 (2006) 427-441. | Numdam | MR 2269202 | Zbl 1110.68122

[14] P. Ochem, Binary words avoiding the pattern AABBCABBA. RAIRO: ITA 44 (2010) 151-158. | Numdam | MR 2604940 | Zbl 1184.68377

[15] A.N. Petrov, Sequence avoiding any complete word. Mathematical Notes of the Academy of Sciences of the USSR 44 (1988) 764-767. | MR 975191 | Zbl 0677.20055

[16] A. Restivo and S. Salemi, Overlap free words on two symbols.In Automata on Infinite Words, edited by M. Nivat and D. Perrin, Ecole de Printemps d'Informatique Théorique, Le Mont Dore, 1984, vol. 192 of Lect. Notes Sci. Springer-Verlag (1985) 198-206. | MR 814744 | Zbl 0572.20038

[17] G. Richomme and F. Wlazinski, About cube-free morphisms. In STACS 2000, Proc. 17th Symp. Theoretical Aspects of Comp. Sci., vol. 1770 of Lect. Notes Sci. Edited by H. Reichel and S. Tison. Springer-Verlag (2000) 99-109. | MR 1781724 | Zbl 0959.68532

[18] P. Roth, Every binary pattern of length six is avoidable on the two-letter alphabet. Acta Informatica 29 (1992) 95-107. | MR 1154583 | Zbl 0741.68083

[19] A.V. Samsonov and A.M. Shur, Binary patterns in binary cube-free words: Avoidability and growth. In Proc. 14th Mons Days of Theoretical Computer Science. Univ. catholique de Louvain, Louvain-la-Neuve (2012) 1-7. electronic. | Zbl pre06379843

[20] A.M. Shur, Binary words avoided by the Thue-Morse sequence. Semigroup Forum 53 (1996) 212-219. | MR 1400647 | Zbl 0859.20048

[21] A.M. Shur, Comparing complexity functions of a language and its extendable part. RAIRO: ITA 42 (2008) 647-655. | Numdam | MR 2434040 | Zbl 1149.68055

[22] A.M. Shur, Growth rates of complexity of power-free languages. Theoret. Comput. Sci. 411 (2010) 3209-3223. | MR 2676864 | Zbl 1196.68121

[23] A.M. Shur, Growth properties of power-free languages. Comput. Sci. Rev. 6 (2012) 187-208. | MR 2862712 | Zbl 1298.68157

[24] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1-67. | JFM 44.0462.01

[25] A.I. Zimin, Blocking sets of terms. Mat. Sbornik 119 (1982) 363-375; In Russian. English translation in Math. USSR Sbornik 47 (1984) 353-364. | MR 678833 | Zbl 0599.20106