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

DOI10.1016/J.JDA.2011.12.002zbMATH Open1273.68288OpenAlexW4205254578MaRDI QIDQ450549FDOQ450549

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

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

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)

Cites Work

• Efficient string matching
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Depth-First Search and Linear Graph Algorithms
• A proof of Golomb's conjecture for the de Bruijn graph
• A Second Course in Formal Languages and Automata Theory
• Unavoidable sets of words of uniform length
• UNAVOIDABLE SETS OF CONSTANT LENGTH
• Unavoidable sets
• Hard counting problems for 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 synchronizing properties of certain prefix codes
• On the complexity of deciding avoidability of sets of partial words
• Unavoidable sets of partial words

Cited In (6)

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

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)