On the Complexity of Deciding Avoidability of Sets of Partial Words

DOI10.1007/978-3-642-02737-6_9MaRDI QIDQ3637218zbMATH OpenOpenAlexFDO

Authors Brandon Blakeley, Josh Gunter, Narad Rampersad, F. Blanchet-Sadri

Publication date 7 July 2009

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02737-6_9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

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

Cites work

• A proof of Golomb's conjecture for the de Bruijn graph
• Algorithmic Combinatorics on Partial Words
• Efficient string matching
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Relationships between nondeterministic and deterministic tape complexities
• Repetition-free words
• Testing avoidability on sets of partial words is hard
• UNAVOIDABLE SETS OF CONSTANT LENGTH
• Unavoidable sets of partial words

Cited in

(11)

• Testing avoidability on sets of partial words is hard
• The complexity of unavoidable word patterns
• Deciding representability of sets of words of equal length in polynomial time
• Minimum number of holes in unavoidable sets of partial words of size three
• Van der Waerden's Theorem and Avoidability in Words
• scientific article; zbMATH DE number 5073567 (Why is no real title available?)
• On the Computational Complexity of Partial Word Automata Problems
• scientific article; zbMATH DE number 6851884 (Why is no real title available?)
• Computational and proof complexity of partial string avoidability
• On the complexity of deciding avoidability of sets of partial words
• Weak containment for partial words is coNP-complete

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 Q3637218)