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

DOI10.1016/J.JDA.2011.12.002MaRDI QIDQ450549zbMATH OpenOpenAlexFDO

Authors Steven Ji, Elizabeth Reiland, F. 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 complexitycombinatorics on wordsNP-hard problemsautomata and formal languagespartial wordsunavoidable sets

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Recommendations

• 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
• Avoidable binary patterns in partial words
• Testing avoidability on sets of partial words is hard

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• A Second Course in Formal Languages and Automata Theory
• A proof of Golomb's conjecture for the de Bruijn graph
• Depth-First Search and Linear Graph Algorithms
• Efficient string matching
• Hard counting problems for partial words
• Minimum number of holes in unavoidable sets of partial words of size three
• On the complexity of deciding avoidability of sets of partial words
• On the synchronizing properties of certain prefix codes
• Testing avoidability on sets of partial words is hard
• UNAVOIDABLE SETS OF CONSTANT LENGTH
• Unavoidable sets
• Unavoidable sets of partial words
• Unavoidable sets of words of uniform length

Cited in

(6)

• Minimum number of holes in unavoidable sets of partial words of size three
• Unary Pattern Avoidance in Partial Words Dense with Holes
• On the Complexity of Deciding Avoidability of Sets of Partial Words
• Unavoidable sets of partial words of uniform length
• Number of holes in unavoidable sets of partial words. I.
• On the complexity of deciding avoidability of sets of partial words

This page was built for publication: Number of holes in unavoidable sets of partial words. II.

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