| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 436222 | Theoretical Computer Science | 2009 | 5 Pages |
Abstract
We prove that the problem of deciding whether a finite set of partial words is unavoidable is NP-hard for any alphabet of size larger than or equal to two, which is in contrast with the well-known feasability results for unavoidability of a set of full words. We raise some related questions on avoidability of sets of partial words.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
