On the Complexity of Deciding Avoidability of Sets of Partial Words

DOI10.1007/978-3-642-02737-6_9zbMath1247.68126OpenAlexW1884971315MaRDI QIDQ3637218

Brandon Blakeley, Narad Rampersad, Josh Gunter, Francine 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)

Related Items (3)

The complexity of unavoidable word patterns ⋮ On the complexity of deciding avoidability of sets of partial words ⋮ Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three

Cites Work

• Unnamed Item
• Unavoidable sets of partial words
• 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
• 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