Unavoidable sets of partial words

DOI10.1007/S00224-008-9106-1zbMath1187.68358OpenAlexW2049228167WikidataQ61719047 ScholiaQ61719047MaRDI QIDQ733729

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

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 wordspartial wordsunavoidable sets

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items (9)

On the complexity of deciding avoidability of sets of partial words ⋮ On universal partial words ⋮ Universal partial words over non-binary alphabets ⋮ Unnamed Item ⋮ Number of holes in unavoidable sets of partial words. I. ⋮ Number of holes in unavoidable sets of partial words. II. ⋮ Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three ⋮ Testing avoidability on sets of partial words is hard ⋮ 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

This page was built for publication: Unavoidable sets of partial words