Pattern avoidance in partial words over a ternary alphabet

• Autorzy: Adam Gągol
• Języki publikacji: EN

Abstrakty

EN

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\cdot 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.

Słowa kluczowe

EN

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

• Wydawca: Wydawnictwo Uniwersytetu Marii Curie-Skłodowskiej
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica
• Rocznik: 2015
• Tom: 69
• Numer: 1

Daty

wydano

2015

online

2015-11-30

Twórcy

autor

Adam Gągol

Bibliografia

• 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.

Identyfikatory

DOI

10.17951/a.2015.69.1.73