Testing avoidability on sets of partial words is hard

DOI10.1016/j.tcs.2008.11.011zbMath1162.68028OpenAlexW2108981141MaRDI QIDQ1006080

Raphaël M. Jungers, Justin Palumbo, Francine Blanchet-Sadri

Publication date: 17 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.11.011

zbMATH Keywords

combinatorics on wordsNP-hard problemspartial wordsunavoidable sets3SAT problem

Mathematics Subject Classification ID

Combinatorics on words (68R15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On the complexity of deciding avoidability of sets of partial words ⋮ Weak containment for partial words is coNP-complete ⋮ Unnamed Item ⋮ Number of holes in unavoidable sets of partial words. II. ⋮ Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three ⋮ Unavoidable sets of partial words ⋮ On the Complexity of Deciding Avoidability of Sets of Partial Words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unavoidable sets of partial words
• On regularity of context-free languages
• On extendibility of unavoidable sets
• Inventories of unavoidable languages and the word-extension conjecture
• Partial words and a theorem of Fine and Wilf
• On the Complexity of Computing the Capacity of Codes That Avoid Forbidden Difference Patterns
• Efficient string matching
• Unavoidable languages, cuts and innocent sets of words
• ALGORITHMIC COMBINATORICS ON PARTIAL WORDS
• Two Element Unavoidable Sets of Partial Words
• DNA Computing