Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431642 | Journal of Discrete Algorithms | 2012 | 10 Pages |
Abstract
Partial words are sequences over a finite alphabet that may contain some undefined positions called holes. We consider unavoidable sets of partial words of equal length. We compute the minimum number of holes in sets of size three over a binary alphabet (summed over all partial words in the sets). We also construct all sets that achieve this minimum. This is a step towards the difficult problem of fully characterizing all unavoidable sets of partial words of size three.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
F. Blanchet-Sadri, Bob Chen, Aleksandar Chakarov,