Weak containment for partial words is coNP-complete

DOI10.1016/J.IPL.2015.09.012MaRDI QIDQ894455zbMATH OpenOpenAlexFDO

Authors 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

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

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
• On quantification of weak sequential completeness
• The hardness of counting full words compatible with partial words

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1953140 (Why is no real title available?)
• Algorithmic Combinatorics on Partial Words
• Containment and equivalence for a fragment of XPath
• On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
• 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

Cited in

(2)

• Hard counting problems for partial words
• The hardness of counting full words compatible with 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)