The hardness of counting full words compatible with partial words

DOI10.1016/J.JCSS.2012.04.001zbMath1280.68099OpenAlexW2034655407MaRDI QIDQ1936243

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

NP-completenesscombinatorics on wordspartial words\(\#\)P complexity class\(\#\)P-complete problems

Mathematics Subject Classification ID

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

Related Items (2)

Weak containment for partial words is coNP-complete ⋮ Subsequences in bounded ranges: matching and analysis problems

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