Testing avoidability on sets of partial words is hard

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Francine Blanchet-Sadri, Professor (Creator)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

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.

Additional Information

Publication
Theoretical Computer Science
Language: English
Date: 2009
Keywords
Computer Science, Combinatorics on words, Partial words, Unavoidable sets, 3SAT problem, NP-hard problems