Number of holes in unavoidable sets of partial words. II.

DOI10.1016/j.jda.2011.12.002zbMath1273.68288MaRDI QIDQ450549

Steven Ji, Elizabeth Reiland, 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

zbMATH Keywords

computational complexity; combinatorics on words; NP-hard problems; automata and formal languages; partial words; unavoidable sets

Mathematics Subject Classification ID

68R15: Combinatorics on words

68Q45: Formal languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

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