Unavoidable sets of partial words of uniform length

MaRDI QIDQ5016356zbMATH OpenFDO

Authors Joey Becker, Laure Flapan, Stephen Watkins, F. Blanchet-Sadri

Publication date 13 December 2021

Full work available at URL https://arxiv.org/abs/1708.06459, http://eptcs.web.cse.unsw.edu.au/paper.cgi?AFL2017.7

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• Minimum number of holes in unavoidable sets of partial words of size three
• Unavoidable sets of partial words
• Testing avoidability on sets of partial words is hard
• Number of holes in unavoidable sets of partial words. I.
• Number of holes in unavoidable sets of partial words. II.

Cites work

• Algorithmic Combinatorics on Partial Words
• An optimal test on finite unavoidable sets of words
• Classifying all avoidable sets of partial words of size two
• Crucial words and the complexity of some extremal problems for sets of prohibited words
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Inventories of unavoidable languages and the word-extension conjecture
• Number of holes in unavoidable sets of partial words. I.
• Number of holes in unavoidable sets of partial words. II.
• On extendibility of unavoidable sets
• On the complexity of deciding avoidability of sets of partial words
• Testing avoidability on sets of partial words is hard
• The length of short words in unavoidable sets
• UNAVOIDABLE AND ALMOST UNAVOIDABLE SETS OF WORDS
• Unavoidable languages, cuts and innocent sets of words
• Unavoidable sets
• UNAVOIDABLE SETS OF CONSTANT LENGTH
• Unavoidable sets of partial words
• Unavoidable sets of words of uniform length

Cited in

(10)

• The complexity of unavoidable word patterns
• Minimum number of holes in unavoidable sets of partial words of size three
• Classifying all avoidable sets of partial words of size two
• Deciding representability of sets of words of equal length
• On the Complexity of Deciding Avoidability of Sets of Partial Words
• Number of holes in unavoidable sets of partial words. I.
• Number of holes in unavoidable sets of partial words. II.
• Two Element Unavoidable Sets of Partial Words
• On the complexity of deciding avoidability of sets of partial words
• Unavoidable sets of partial words

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

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