Open AccessPattern avoidance in partial words over a ternary alphabet
Author(s) -
Adam Gągol
Publication year - 2015
Publication title -
annales universitatis mariae curie-skłodowska. sectio a, mathematica
Language(s) - English
Resource type - Journals
eISSN - 2083-7402
pISSN - 0365-1029
DOI - 10.17951/a.2015.69.1.73
Subject(s) - alphabet , ternary operation , conjecture , mathematics , combinatorics , binary number , discrete mathematics , arithmetic , computer science , linguistics , philosophy , programming language
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.