Pattern avoidance in partial words over a ternary alphabet
Adam Gągol
Annales UMCS, Mathematica, Tome 68 (2015), p. 73-82 / 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:270921 
@article{bwmeta1.element.doi-10_1515_umcsmath-2015-0013,
     author = {Adam G\k agol},
     title = {Pattern avoidance in partial words over a ternary alphabet},
     journal = {Annales UMCS, Mathematica},
     volume = {68},
     year = {2015},
     pages = {73-82},
     zbl = {1329.68198},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_1515_umcsmath-2015-0013}
}

Adam Gągol. Pattern avoidance in partial words over a ternary alphabet. Annales UMCS, Mathematica, Tome 68 (2015) pp. 73-82. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_1515_umcsmath-2015-0013/

[1] Blanchet-Sadri, F., Woodhouse, B., Strict Bounds for Pattern Avoidance, Theoret. Comput. Sci. 506 (2013), 17-28. | Zbl 1301.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. | Zbl 1165.05001

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

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

[6] Lothaire, M., Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, 2002. | Zbl 1001.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. | Zbl 1300.60024

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

[9] Zydroń, A., Unikalność bezjednostkowych wzorcow o dużej liczbie zmiennych, MsC Thesis, Jagiellonian University, 2013.