On the complexity of deciding avoidability of sets of partial words

DOI10.1016/J.TCS.2010.09.006zbMATH Open1208.68164OpenAlexW2129749965MaRDI QIDQ606993FDOQ606993

Brandon Blakeley, F. 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

Recommendations

• On the Complexity of Deciding Avoidability of Sets of Partial Words
• Testing avoidability on sets of partial words is hard
• Unavoidable sets of partial words of uniform length
• Number of holes in unavoidable sets of partial words. II.
• scientific article; zbMATH DE number 6851884

zbMATH Keywords

computational complexitycombinatorics on wordsde Bruijn graphsNP-hard problemspartial wordsunavoidable sets

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• On the Complexity of Deciding Avoidability of Sets of Partial Words
• Title not available (Why is that?)
• On the Computational Complexity of Partial Word Automata Problems
• Title not available (Why is that?)
• Number of holes in unavoidable sets of partial words. II.
• Title not available (Why is that?)
• Testing avoidability on sets of partial words is hard
• Weak containment for partial words is coNP-complete
• On universal partial words
• Van der Waerden's Theorem and Avoidability in Words

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q606993)