Geodesic
Pattern avoidance in partial words over a ternary alphabet
Annales Universitatis Mariae Curie-Skłodowska. Mathematica , Tome 69 (2015) no. 1.

Voir la notice de l'article provenant de la source Library of Science

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 2^m is avoidable over a ternary alphabet and if the length is at least 3· 2^m-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.
Keywords: Formal languages, combinatorics on words, pattern avoidance, partial words, entropy compression, probabilistic method 
@article{AUM_2015_69_1_a4,
     author = {G\k{a}gol, Adam},
     title = {Pattern avoidance in partial words over a ternary alphabet},
     journal = {Annales Universitatis Mariae Curie-Sk{\l}odowska. Mathematica },
     publisher = {mathdoc},
     volume = {69},
     number = {1},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/AUM_2015_69_1_a4/}
}
TY  - JOUR
AU  - Gągol, Adam
TI  - Pattern avoidance in partial words over a ternary alphabet
JO  - Annales Universitatis Mariae Curie-Skłodowska. Mathematica 
PY  - 2015
VL  - 69
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AUM_2015_69_1_a4/
LA  - en
ID  - AUM_2015_69_1_a4
ER  - 
%0 Journal Article
%A Gągol, Adam
%T Pattern avoidance in partial words over a ternary alphabet
%J Annales Universitatis Mariae Curie-Skłodowska. Mathematica 
%D 2015
%V 69
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AUM_2015_69_1_a4/
%G en
%F AUM_2015_69_1_a4
Gągol, Adam. Pattern avoidance in partial words over a ternary alphabet. Annales Universitatis Mariae Curie-Skłodowska. Mathematica , Tome 69 (2015) no. 1. http://geodesic.mathdoc.fr/item/AUM_2015_69_1_a4/

[1] Blanchet-Sadri, F., Woodhouse, B., Strict Bounds for Pattern Avoidance, Theoret. Comput. Sci. 506 (2013), 17–28.

[2] Cassaigne, J., Motifs evitables et regularites dans les mots, PhD Thesis, Universite Paris VI, July 1994.

[3] Flajolet, P., Sedgewick, R., Analytic Combinatorics. Cambridge University Press, 2009, ISBN 978-0-521-89806-5, electronic version.

[4] Grytczuk, J., Kozik, J., Micek, P., A new approach to nonrepetitive sequences, Random Structures Algorithms 42 (2013), 214–225.

[5] Krieger, D., Ochem, P., Rampersad, N., Shallit, J., Avoiding Approximate Squares, Lecture Notes in Computer Science, Vol. 4588, 2007, 278–289.

[6] Lothaire, M., Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, 2002.

[7] Moser, R. A., Tardos, G., A constructive proof of the general lovasz local lemma, J. ACM 57 (2) (2010), Art. 11, 15 pp.

[8] Ochem, P., Pinlou, A., Application of entropy compression in pattern avoidance, Electron. J. Combin. 21, P2.7 (2014).

[9] Zydron, A., Unikalność bezjednostkowych wzorców o dużej liczbie zmiennych, MsC Thesis, Jagiellonian University, 2013.