Pattern avoidance in partial words over a ternary alphabet
Annales UMCS, Mathematica (2015)
- Volume: 69, Issue: 1, page 73-82
- ISSN: 2083-7402
Access Full Article
top
Abstract
topHow to cite
topAdam Gągol. "Pattern avoidance in partial words over a ternary alphabet." Annales UMCS, Mathematica 69.1 (2015): 73-82. <http://eudml.org/doc/270921>.
@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 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},
author = {Adam Gągol},
journal = {Annales UMCS, Mathematica},
keywords = {Formal languages; combinatorics on words; pattern avoidance; partial words; entropy compression; probabilistic method; formal languages},
language = {eng},
number = {1},
pages = {73-82},
title = {Pattern avoidance in partial words over a ternary alphabet},
url = {http://eudml.org/doc/270921},
volume = {69},
year = {2015},
}
TY - JOUR
AU - Adam Gągol
TI - Pattern avoidance in partial words over a ternary alphabet
JO - Annales UMCS, Mathematica
PY - 2015
VL - 69
IS - 1
SP - 73
EP - 82
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 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
LA - eng
KW - Formal languages; combinatorics on words; pattern avoidance; partial words; entropy compression; probabilistic method; formal languages
UR - http://eudml.org/doc/270921
ER -
References
top- [1] Blanchet-Sadri, F., Woodhouse, B., Strict Bounds for Pattern Avoidance, Theoret. Comput. Sci. 506 (2013), 17-28. Zbl1301.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. Zbl1165.05001
- [4] Grytczuk, J., Kozik, J., Micek, P., A new approach to nonrepetitive sequences, Random Structures Algorithms 42 (2013), 214-225. Zbl06143746
- [5] Krieger, D., Ochem, P., Rampersad, N., Shallit, J., Avoiding Approximate Squares, Lecture Notes in Computer Science, Vol. 4588, 2007, 278-289. Zbl1202.68296
- [6] Lothaire, M., Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, 2002. Zbl1001.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. Zbl1300.60024
- [8] Ochem, P., Pinlou, A., Application of entropy compression in pattern avoidance, Electron. J. Combin. 21, P2.7 (2014). Zbl1299.68046
- [9] Zydroń, A., Unikalność bezjednostkowych wzorcow 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.