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.
Testing avoidability on sets of partial words is hard
PDF (Portable Document Format)
295 KB
Created on 8/2/2011
Views: 2133
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