# Pattern avoidance in partial words over a ternary alphabet

Annales UMCS, Mathematica (2015)

- Volume: 69, Issue: 1, page 73-82
- ISSN: 2083-7402

## Access Full Article

top## Abstract

top## How to cite

topAdam Gągol. "Pattern avoidance in partial words over a ternary alphabet." Annales UMCS, Mathematica 69.1 (2015): 73-82. <http://eudml.org/doc/270921>.

@article{AdamGągol2015,

abstract = {Blanched-Sadri and Woodhouse in 2013 have proven the conjecture of Cassaigne, stating that any pattern with m distinct variables and of length at least 2m is avoidable over a ternary alphabet and if the length is at least 3 2m−1 it is avoidable over a binary alphabet. They conjectured that similar theorems are true for partial words - sequences, in which some characters are left “blank”. Using method of entropy compression, we obtain the partial words version of the theorem for ternary words},

author = {Adam Gągol},

journal = {Annales UMCS, Mathematica},

keywords = {Formal languages; combinatorics on words; pattern avoidance; partial words; entropy compression; probabilistic method; formal languages},

language = {eng},

number = {1},

pages = {73-82},

title = {Pattern avoidance in partial words over a ternary alphabet},

url = {http://eudml.org/doc/270921},

volume = {69},

year = {2015},

}

TY - JOUR

AU - Adam Gągol

TI - Pattern avoidance in partial words over a ternary alphabet

JO - Annales UMCS, Mathematica

PY - 2015

VL - 69

IS - 1

SP - 73

EP - 82

AB - Blanched-Sadri and Woodhouse in 2013 have proven the conjecture of Cassaigne, stating that any pattern with m distinct variables and of length at least 2m is avoidable over a ternary alphabet and if the length is at least 3 2m−1 it is avoidable over a binary alphabet. They conjectured that similar theorems are true for partial words - sequences, in which some characters are left “blank”. Using method of entropy compression, we obtain the partial words version of the theorem for ternary words

LA - eng

KW - Formal languages; combinatorics on words; pattern avoidance; partial words; entropy compression; probabilistic method; formal languages

UR - http://eudml.org/doc/270921

ER -

## References

top- [1] Blanchet-Sadri, F., Woodhouse, B., Strict Bounds for Pattern Avoidance, Theoret. Comput. Sci. 506 (2013), 17-28. Zbl1301.68209
- [2] Cassaigne, J., Motifs ´evitables et r´egularit´es dans les mots, PhD Thesis, Universit´e Paris VI, July 1994.
- [3] Flajolet, P., Sedgewick, R., Analytic Combinatorics. Cambridge University Press, 2009, ISBN 978-0-521-89806-5, electronic version. Zbl1165.05001
- [4] Grytczuk, J., Kozik, J., Micek, P., A new approach to nonrepetitive sequences, Random Structures Algorithms 42 (2013), 214-225. Zbl06143746
- [5] Krieger, D., Ochem, P., Rampersad, N., Shallit, J., Avoiding Approximate Squares, Lecture Notes in Computer Science, Vol. 4588, 2007, 278-289. Zbl1202.68296
- [6] Lothaire, M., Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, 2002. Zbl1001.68093
- [7] Moser, R. A., Tardos, G., A constructive proof of the general lovasz local lemma, J. ACM 57 (2) (2010), Art. 11, 15 pp. Zbl1300.60024
- [8] Ochem, P., Pinlou, A., Application of entropy compression in pattern avoidance, Electron. J. Combin. 21, P2.7 (2014). Zbl1299.68046
- [9] Zydroń, A., Unikalność bezjednostkowych wzorcow o dużej liczbie zmiennych, MsC Thesis, Jagiellonian University, 2013.

## NotesEmbed ?

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