Number of Holes in Unavoidable Sets of Partial Words II
- 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 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.
Number of Holes in Unavoidable Sets of Partial Words II
PDF (Portable Document Format)
199 KB
Created on 6/26/2014
Views: 1501
Additional Information
- Publication
- Journal of Discrete Algorithms, 14, 65-73
- Language: English
- Date: 2012
- Keywords
- Automata and formal languages, Computational complexity, Combinatorics on words, Partial words, Unavoidable sets, NP-hard problems