Pattern avoidance in partial words over a ternary alphabet
Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica (2015)
- Volume: 69, Issue: 1
- ISSN: 0365-1029
Access Full Article
top
Abstract
topHow to cite
topAdam Gągol. "Pattern avoidance in partial words over a ternary alphabet." Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica 69.1 (2015): null. <http://eudml.org/doc/289846>.
@article{AdamGągol2015,
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.},
author = {Adam Gągol},
journal = {Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica},
keywords = {Formal languages; combinatorics on words; pattern avoidance; partial words; entropy compression; probabilistic method},
language = {eng},
number = {1},
pages = {null},
title = {Pattern avoidance in partial words over a ternary alphabet},
url = {http://eudml.org/doc/289846},
volume = {69},
year = {2015},
}
TY - JOUR
AU - Adam Gągol
TI - Pattern avoidance in partial words over a ternary alphabet
JO - Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica
PY - 2015
VL - 69
IS - 1
SP - null
AB - 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.
LA - eng
KW - Formal languages; combinatorics on words; pattern avoidance; partial words; entropy compression; probabilistic method
UR - http://eudml.org/doc/289846
ER -
References
top- 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.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.