Hard counting problems for partial words

DOI10.1007/978-3-642-13089-2_36zbMATH Open1284.68487OpenAlexW19005284MaRDI QIDQ3564883FDOQ3564883

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

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

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)

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)