Pattern avoidance in partial words over a ternary alphabet

Adam Gągol

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

Keywords


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

Full Text:

PDF

References


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.




DOI: http://dx.doi.org/10.17951/a.2015.69.1.73
Date of publication: 2015-11-30 09:21:11
Date of submission: 2015-09-03 12:33:44


Statistics


Total abstract view - 659
Downloads (from 2020-06-17) - PDF - 525

Indicators



Refbacks

  • There are currently no refbacks.


Copyright (c) 2015 Adam Gągol