Weak containment for partial words is coNP-complete

DOI10.1016/J.IPL.2015.09.012zbMATH Open1346.68104OpenAlexW1792989921MaRDI QIDQ894455FDOQ894455

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

Recommendations

• Partial words and a theorem of Fine and Wilf revisited
• Fine and Wilf's theorem for partial words with arbitrarily many weak periods
• scientific article; zbMATH DE number 7695589
• Partial words and a theorem of Fine and Wilf
• On the Complexity of Deciding Avoidability of Sets of Partial Words
• On the complexity of deciding avoidability of sets of partial words
• Covering problems for partial words and for indeterminate strings
• Covering problems for partial words and for indeterminate strings
• On quantification of weak sequential completeness
• The hardness of counting full words compatible with partial words

zbMATH Keywords

computational complexityNP-completenessformal languagespartial wordslanguage containment

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

• Title not available (Why is that?)
• On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
• Containment and equivalence for a fragment of XPath
• Algorithmic Combinatorics on Partial Words
• Title not available (Why is that?)
• Testing avoidability on sets of partial words is hard
• On the complexity of deciding avoidability of sets of partial words
• The hardness of counting full words compatible with partial words

Cited In (1)

• Hard counting problems for partial words

This page was built for publication: Weak containment for partial words is coNP-complete

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