Hard counting problems for partial words

DOI10.1007/978-3-642-13089-2_36MaRDI QIDQ3564883zbMATH OpenOpenAlexFDO

Authors Florin Manea, Cătălin Tiseanu

Publication date 26 May 2010

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13089-2_36

zbMATH Keywords

combinatorics on wordsNP-completenesspartial words{\#}P complexity class{\#}P-complete problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Recommendations

• The hardness of counting full words compatible with partial words
• On the Computational Complexity of Partial Word Automata Problems
• Testing avoidability on sets of partial words is hard
• Counting distinct squares in partial words
• Weak containment for partial words is coNP-complete

Cited in

(6)

• On minimal Sturmian partial words
• Regular languages of partial words
• Constructing partial words with subword complexities not achievable by full words
• Number of holes in unavoidable sets of partial words. II.
• Efficient enumeration of non-equivalent squares in partial words with few holes
• The hardness of counting full words compatible with partial words

This page was built for publication: Hard counting problems for partial words

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