Pattern avoidance in partial words over a ternary alphabet
Adam Gągol
Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica, Tome 69 (2015), / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2015-01-01
EUDML-ID : urn:eudml:doc:289846 
@article{bwmeta1.element.ojs-doi-10_17951_a_2015_69_1_73,
     author = {Adam G\k agol},
     title = {Pattern avoidance in partial words over a ternary alphabet},
     journal = {Annales Universitatis Mariae Curie-Sk\l odowska, sectio A -- Mathematica},
     volume = {69},
     year = {2015},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.ojs-doi-10_17951_a_2015_69_1_73}
}

Adam Gągol. Pattern avoidance in partial words over a ternary alphabet. Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica, Tome 69 (2015) . http://gdmltest.u-ga.fr/item/bwmeta1.element.ojs-doi-10_17951_a_2015_69_1_73/

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

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

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

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

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

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

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

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

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