Unavoidable sets of partial words

DOI10.1007/S00224-008-9106-1zbMATH Open1187.68358DBLPjournals/mst/Blanchet-SadriBKPW09OpenAlexW2049228167WikidataQ61719047 ScholiaQ61719047MaRDI QIDQ733729FDOQ733729

Andy Kalcic, T. Weyand, Justin Palumbo, F. Blanchet-Sadri, N. C. Brownstein

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

Recommendations

• Two Element Unavoidable Sets of Partial Words
• Number of holes in unavoidable sets of partial words. I.
• Minimum number of holes in unavoidable sets of partial words of size three
• Unavoidable sets of partial words of uniform length
• Open problems on avoidable patterns in partial words

zbMATH Keywords

combinatorics on wordspartial wordsunavoidable sets

Mathematics Subject Classification ID

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

Cites Work

• Efficient string matching
• Every binary pattern of length six is avoidable on the two-letter alphabet
• Unavoidable binary patterns
• Title not available (Why is that?)
• DNA Computing
• Algorithmic Combinatorics on Partial Words
• Partial words and a theorem of Fine and Wilf
• On the Complexity of Computing the Capacity of Codes That Avoid Forbidden Difference Patterns
• Testing avoidability on sets of partial words is hard
• On extendibility of unavoidable sets
• Inventories of unavoidable languages and the word-extension conjecture
• Unavoidable languages, cuts and innocent sets of words
• On regularity of context-free languages
• Two Element Unavoidable Sets of Partial Words

Cited In (12)

• On the Complexity of Deciding Avoidability of Sets of Partial Words
• Two Element Unavoidable Sets of Partial Words
• 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
• Title not available (Why is that?)
• Testing avoidability on sets of partial words is hard
• On universal partial words
• Universal partial words over non-binary alphabets
• Recurrent Partial Words and Representable Sets.
• On Unavoidable Sets of Word Patterns
• Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q733729)