Covering problems for partial words and for indeterminate strings

DOI10.1016/j.tcs.2017.05.026zbMath1380.68468arXiv1412.3696OpenAlexW2622971911WikidataQ61677845 ScholiaQ61677845MaRDI QIDQ1676304

Tomasz Kociumaka, Costas S. Iliopoulos, Wojciech Rytter, Maxime Crochemore, Jakub Radoszewski, Tomasz Walen

Publication date: 6 November 2017

Published in: Theoretical Computer Science, Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.3696

zbMATH Keywords

fixed-parameter tractabilitypartial wordcover of a wordindeterminate stringstring with don't cares

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items (13)

String covers of a tree ⋮ Covering problems for partial words and for indeterminate strings ⋮ Maximal degenerate palindromes with gaps and mismatches ⋮ String Covering: A Survey ⋮ Period recovery of strings over the Hamming and edit distances ⋮ Crochemore's partitioning on weighted strings and applications ⋮ Experimental evaluation of algorithms for computing quasiperiods ⋮ Efficient Computation of 2-Covers of a String. ⋮ IDPM: An Improved Degenerate Pattern Matching Algorithm for Biological Sequences ⋮ Unnamed Item ⋮ Approximate pattern matching on elastic-degenerate text ⋮ Comparing Degenerate Strings ⋮ Approximate cover of strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing covers using prefix tables
• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• Simple deterministic wildcard matching
• Fast pattern-matching on indeterminate strings
• Efficient string matching with k mismatches
• Parallel string matching with k mismatches
• An on-line string superprimitivity test
• Which problems have strongly exponential complexity?
• Covering problems for partial words and for indeterminate strings
• Covering a string
• Non-standard stringology
• Verifying candidate matches in sparse and wildcard matching
• AN ADAPTIVE HYBRID PATTERN-MATCHING ALGORITHM ON INDETERMINATE STRINGS
• Generalized String Matching
• A Linear-Time Algorithm for Seeds Computation
• Algorithmic Combinatorics on Partial Words
• Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.
• Algorithms on Strings
• On the complexity of \(k\)-SAT
• Computing the cover array in linear time

This page was built for publication: Covering problems for partial words and for indeterminate strings