On the complexity of deciding avoidability of sets of partial words

DOI10.1016/j.tcs.2010.09.006zbMath1208.68164OpenAlexW2129749965MaRDI QIDQ606993

Brandon Blakeley, Francine Blanchet-Sadri, Narad Rampersad, Josh Gunter

Publication date: 19 November 2010

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

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

zbMATH Keywords

computational complexitycombinatorics on wordsNP-hard problemsde Bruijn graphspartial wordsunavoidable sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Related Items (4)

Weak containment for partial words is coNP-complete ⋮ On universal partial words ⋮ Unnamed Item ⋮ Number of holes in unavoidable sets of partial words. II.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Crucial words and the complexity of some extremal problems for sets of prohibited words
• Unavoidable sets of partial words
• Simple deterministic wildcard matching
• Testing avoidability on sets of partial words is hard
• Repetition-free words
• Relationships between nondeterministic and deterministic tape complexities
• A proof of Golomb's conjecture for the de Bruijn graph
• On the Complexity of Deciding Avoidability of Sets of Partial Words
• Efficient string matching
• Algorithmic Combinatorics on Partial Words
• UNAVOIDABLE SETS OF CONSTANT LENGTH

This page was built for publication: On the complexity of deciding avoidability of sets of partial words