Binary words avoiding the pattern AABBCABBA

Pascal Ochem

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 44, Issue: 1, page 151-158
  • ISSN: 0988-3754

Abstract

top
We show that there are three types of infinite words over the two-letter alphabet {0,1} that avoid the pattern AABBCABBA. These types, P, E0, and E1, differ by the factor complexity and the asymptotic frequency of the letter 0. Type P has polynomial factor complexity and letter frequency 1 2 . Type E0 has exponential factor complexity and the frequency of the letter 0 is at least 0.45622 and at most 0.48684. Type E1 is obtained from type E0 by exchanging 0 and 1.

How to cite

top

Ochem, Pascal. "Binary words avoiding the pattern AABBCABBA." RAIRO - Theoretical Informatics and Applications 44.1 (2010): 151-158. <http://eudml.org/doc/250803>.

@article{Ochem2010,
abstract = { We show that there are three types of infinite words over the two-letter alphabet \{0,1\} that avoid the pattern AABBCABBA. These types, P, E0, and E1, differ by the factor complexity and the asymptotic frequency of the letter 0. Type P has polynomial factor complexity and letter frequency $\frac\{1\}\{2\}$. Type E0 has exponential factor complexity and the frequency of the letter 0 is at least 0.45622 and at most 0.48684. Type E1 is obtained from type E0 by exchanging 0 and 1. },
author = {Ochem, Pascal},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Combinatorics on words; letter frequency; factor complexity; combinatorics on words},
language = {eng},
month = {2},
number = {1},
pages = {151-158},
publisher = {EDP Sciences},
title = {Binary words avoiding the pattern AABBCABBA},
url = {http://eudml.org/doc/250803},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Ochem, Pascal
TI - Binary words avoiding the pattern AABBCABBA
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/2//
PB - EDP Sciences
VL - 44
IS - 1
SP - 151
EP - 158
AB - We show that there are three types of infinite words over the two-letter alphabet {0,1} that avoid the pattern AABBCABBA. These types, P, E0, and E1, differ by the factor complexity and the asymptotic frequency of the letter 0. Type P has polynomial factor complexity and letter frequency $\frac{1}{2}$. Type E0 has exponential factor complexity and the frequency of the letter 0 is at least 0.45622 and at most 0.48684. Type E1 is obtained from type E0 by exchanging 0 and 1.
LA - eng
KW - Combinatorics on words; letter frequency; factor complexity; combinatorics on words
UR - http://eudml.org/doc/250803
ER -

References

top
  1. K.A. Baker, G.F. McNulty and W. Taylor, Growth problems for avoidable words. Theoret. Comput. Sci.69 (1989) 319–345.  
  2. J. Berstel, Axel Thue's papers on repetitions in words: a translation. Publications du LaCIM, Département de mathématiques et d'informatique 95, Université du Québec à Montréal (1995). berstel/Articles/1994ThueTranslation.pdf  URIhttp://www-igm.univ-mlv.fr/
  3. J. Berstel, Growth of repetition-free words - a review. Theoret. Comput. Sci.340 (2005) 280–290.  
  4. J. Cassaigne, Motifs évitables et régularité dans les mots. Thèse de Doctorat, Université Paris VI (1994).  
  5. R.J. Clark, Avoidable formulas in combinatorics on words. Ph.D. thesis, University of California, Los Angeles (2001).  
  6. R. Kolpakov, Efficient lower bounds on the number of repetition-free words. J. Integer Sequences10 (2007) Article 07.3.2.  
  7. P. Ochem, A generator of morphisms for infinite words. RAIRO-Theor. Inf. Appl.40 (2006) 427–441.  
  8. P. Ochem, Letter frequency in infinite repetition-free words. Theoret. Comput. Sci.380 (2007) 388–392.  
  9. P. Ochem and T. Reix, Upper bound on the number of ternary square-free words, Proceedings of the Workshop on Words and Automata (WOWA'06) (St Petersburg, June 2006). ochem/morphisms/wowa.ps  URIhttp://www.lri.fr/
  10. A.M. Shur, Combinatorial complexity of regular languages. CSR 2008. Lect. Notes Comput. Sci.5010 (2008) 289–301.  
  11. A.I. Zimin, Blocking sets of terms. Math. USSR Sbornik47 (1984) 353–364. English translation.  

NotesEmbed ?

top

You must be logged in to post comments.