The hardness of counting full words compatible with partial words

DOI10.1016/J.JCSS.2012.04.001MaRDI QIDQ1936243zbMATH OpenOpenAlexFDO

Authors Florin Manea, Cătălin Tiseanu

Publication date 21 February 2013

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2012.04.001

zbMATH Keywords

\(\#\)P complexity class\(\#\)P-complete problemscombinatorics on wordsNP-completenesspartial words

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Recommendations

• Hard counting problems for partial words
• On the Computational Complexity of Partial Word Automata Problems
• Testing avoidability on sets of partial words is hard
• Weak containment for partial words is coNP-complete
• Counting bordered partial words by critical positions

Cited in

(5)

• Testing avoidability on sets of partial words is hard
• Hard counting problems for partial words
• Subsequences in bounded ranges: matching and analysis problems
• k-universality of regular languages
• Weak containment for partial words is coNP-complete

This page was built for publication: The hardness of counting full words compatible with partial words

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