Unavoidable sets of partial words

DOI10.1007/s00224-008-9106-1zbMath1187.68358WikidataQ61719047 ScholiaQ61719047MaRDI QIDQ733729

Francine Blanchet-Sadri, N. C. Brownstein, Andy Kalcic, Justin Palumbo, Tracy Weyand

Publication date: 19 October 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://libres.uncg.edu/ir/uncg/f/F_Blanchet-Sadri_Unavoidable_2009.pdf

zbMATH Keywords

combinatorics on words; partial words; unavoidable sets

Mathematics Subject Classification ID

68R15: Combinatorics on words

68Q45: Formal languages and automata

Related Items

Number of holes in unavoidable sets of partial words. I., Number of holes in unavoidable sets of partial words. II., On the complexity of deciding avoidability of sets of partial words, Testing avoidability on sets of partial words is hard, Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three, On the Complexity of Deciding Avoidability of Sets of Partial Words

Cites Work

• Unnamed Item
• 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
• Every binary pattern of length six is avoidable on the two-letter alphabet
• Partial words and a theorem of Fine and Wilf
• Unavoidable binary patterns
• On the Complexity of Computing the Capacity of Codes That Avoid Forbidden Difference Patterns
• Efficient string matching
• Unavoidable languages, cuts and innocent sets of words
• Algorithmic Combinatorics on Partial Words
• Two Element Unavoidable Sets of Partial Words
• DNA Computing