Weak containment for partial words is coNP-complete

DOI10.1016/j.ipl.2015.09.012zbMath1346.68104OpenAlexW1792989921MaRDI QIDQ894455

Paweł Parys

Publication date: 1 December 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.09.012

zbMATH Keywords

computational complexityNP-completenessformal languagespartial wordslanguage containment

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of deciding avoidability of sets of partial words
• Testing avoidability on sets of partial words is hard
• The hardness of counting full words compatible with partial words
• Algorithmic Combinatorics on Partial Words
• On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
• Containment and equivalence for a fragment of XPath