Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431643 | Journal of Discrete Algorithms | 2012 | 9 Pages |
Abstract
We are concerned with the complexity of deciding the avoidability of sets of partial words over an arbitrary alphabet. Towards this, we investigate the minimum size of unavoidable sets of partial words with a fixed number of holes. Additionally, we analyze the complexity of variations on the decision problem when placing restrictions on the number of holes and length of the words.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
F. Blanchet-Sadri, Steven Ji, Elizabeth Reiland,