Number of holes in unavoidable sets of partial words. II.
From MaRDI portal
Publication:450549
DOI10.1016/j.jda.2011.12.002zbMath1273.68288OpenAlexW4205254578MaRDI QIDQ450549
Elizabeth Reiland, Steven Ji, Francine Blanchet-Sadri
Publication date: 13 September 2012
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2011.12.002
computational complexitycombinatorics on wordsNP-hard problemsautomata and formal languagespartial wordsunavoidable sets
Combinatorics on words (68R15) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of deciding avoidability of sets of partial words
- Unavoidable sets of partial words
- Testing avoidability on sets of partial words is hard
- Unavoidable sets of words of uniform length
- A proof of Golomb's conjecture for the de Bruijn graph
- Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three
- A Second Course in Formal Languages and Automata Theory
- Hard Counting Problems for Partial Words
- Efficient string matching
- Depth-First Search and Linear Graph Algorithms
- UNAVOIDABLE SETS OF CONSTANT LENGTH
- On the synchronizing properties of certain prefix codes
- Unavoidable sets