On the Complexity of Deciding Avoidability of Sets of Partial Words
From MaRDI portal
Publication:3637218
DOI10.1007/978-3-642-02737-6_9zbMath1247.68126MaRDI 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
Related Items
On the complexity of deciding avoidability of sets of partial words, The complexity of unavoidable word patterns, 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