Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three

DOI10.1007/978-3-642-19222-7_6zbMath1232.68096OpenAlexW1652965943MaRDI QIDQ3000493

Aleksandar Chakarov, Bob Chen, Francine Blanchet-Sadri

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_6

zbMATH Keywords

combinatorics on wordspartial wordsunavoidable

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Crucial words and the complexity of some extremal problems for sets of prohibited words
• Unavoidable sets of partial words
• On regularity of context-free languages
• Testing avoidability on sets of partial words is hard
• On extendibility of unavoidable sets
• Inventories of unavoidable languages and the word-extension conjecture
• An optimal test on finite unavoidable sets of words
• Unavoidable sets of words of uniform length
• A proof of Golomb's conjecture for the de Bruijn graph
• On the Complexity of Deciding Avoidability of Sets of Partial Words
• Unavoidable languages, cuts and innocent sets of words
• Algorithmic Combinatorics on Partial Words
• UNAVOIDABLE SETS OF CONSTANT LENGTH
• On the synchronizing properties of certain prefix codes
• Unavoidable sets