Binary patterns in binary cube-free words: Avoidability and growth

Robert Mercaş; Pascal Ochem; Alexey V. Samsonov; Arseny M. Shur

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

  • Volume: 48, Issue: 4, page 369-389
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Mercaş, Robert, et al. "Binary patterns in binary cube-free words: Avoidability and growth." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.4 (2014): 369-389. <http://eudml.org/doc/273030>.

@article{Mercaş2014,
abstract = {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.},
author = {Mercaş, Robert, Ochem, Pascal, Samsonov, Alexey V., Shur, Arseny M.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {formal languages; avoidability; avoidable pattern; cube-free word; overlap-free word; growth rate; morphism},
language = {eng},
number = {4},
pages = {369-389},
publisher = {EDP-Sciences},
title = {Binary patterns in binary cube-free words: Avoidability and growth},
url = {http://eudml.org/doc/273030},
volume = {48},
year = {2014},
}

TY - JOUR
AU - Mercaş, Robert
AU - Ochem, Pascal
AU - Samsonov, Alexey V.
AU - Shur, Arseny M.
TI - Binary patterns in binary cube-free words: Avoidability and growth
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2014
PB - EDP-Sciences
VL - 48
IS - 4
SP - 369
EP - 389
AB - 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.
LA - eng
KW - formal languages; avoidability; avoidable pattern; cube-free word; overlap-free word; growth rate; morphism
UR - http://eudml.org/doc/273030
ER -

References

top
  1. [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. [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. Zbl1217.68164MR2862710
  3. [3] K.A. Baker, G.F. McNulty and W. Taylor, Growth problems for avoidable words. Theoret. Comput. Sci.69 (1989) 319–345. Zbl0693.68039MR1036470
  4. [4] D.A. Bean, A. Ehrenfeucht and G. McNulty, Avoidable patterns in strings of symbols. Pacific J. Math.85 (1979) 261–294. Zbl0428.05001MR574919
  5. [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. Zbl1127.68073MR2334234
  6. [6] V.D. Blondel, J. Cassaigne and R. Jungers, On the number of α-power-free binary words for 2 &lt;α ≤ 7/3. Theoret. Comput. Sci. 410 (2009) 2823–2833. Zbl1173.68046MR2543336
  7. [7] F.-J. Brandenburg, Uniformly growing k-th power-free homomorphisms. Theoret. Comput. Sci.23 (1983) 69–82. Zbl0508.68051MR693069
  8. [8] J. Cassaigne, Unavoidable binary patterns. Acta Informatica30 (1993) 385–395. Zbl0790.68096MR1227889
  9. [9] J. Cassaigne, Motifs évitables et régularités dans les mots (Thèse de Doctorat). Tech. Report. LITP-TH 94-04 (1994). 
  10. [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. Zbl0866.68057MR1469998
  11. [11] P. Goralcik and T. Vanicek, Binary patterns in binary words. Internat. J. Algebra Comput.1 (1991) 387–391. Zbl0759.68051MR1148238
  12. [12] J. Karhumäki and J. Shallit, Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory. Ser. A104 (2004) 335–347. Zbl1065.68080MR2046086
  13. [13] P. Ochem, A generator of morphisms for infinite words. RAIRO: ITA 40 (2006) 427–441. Zbl1110.68122MR2269202
  14. [14] P. Ochem, Binary words avoiding the pattern AABBCABBA. RAIRO: ITA 44 (2010) 151–158. Zbl1184.68377MR2604940
  15. [15] A.N. Petrov, Sequence avoiding any complete word. Mathematical Notes of the Academy of Sciences of the USSR44 (1988) 764–767. Zbl0677.20055MR975191
  16. [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. Zbl0572.20038MR814744
  17. [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. Zbl0959.68532MR1781724
  18. [18] P. Roth, Every binary pattern of length six is avoidable on the two-letter alphabet. Acta Informatica29 (1992) 95–107. Zbl0741.68083MR1154583
  19. [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. Zbl1302.68228
  20. [20] A.M. Shur, Binary words avoided by the Thue–Morse sequence. Semigroup Forum53 (1996) 212–219. Zbl0859.20048MR1400647
  21. [21] A.M. Shur, Comparing complexity functions of a language and its extendable part. RAIRO: ITA 42 (2008) 647–655. Zbl1149.68055MR2434040
  22. [22] A.M. Shur, Growth rates of complexity of power-free languages. Theoret. Comput. Sci.411 (2010) 3209–3223. Zbl1196.68121MR2676864
  23. [23] A.M. Shur, Growth properties of power-free languages. Comput. Sci. Rev.6 (2012) 187–208. Zbl1298.68157MR2862712
  24. [24] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1–67. Zbl44.0462.01JFM44.0462.01
  25. [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. Zbl0599.20106MR678833

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.