Elastic-degenerate string comparison

DOI10.1016/J.IC.2025.105296MaRDI QIDQ6982305zbMATH OpenFDO

Authors Esteban Gabory, Moses Njagi Mwaniki, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski, Michelle Sweering, Wiktor Zuba

Publication date 19 May 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105296

zbMATH Keywords

acronym identificationelastic-degenerate stringlanguages intersectionpangenomesequence comparison

Mathematics Subject Classification ID

Algorithms on strings (68W32) Analysis of algorithms (68W40)

Cites work

• A new algorithm for optimal 2-constraint satisfaction and its implications
• A simple algorithm for identifying abbreviation definitions in biomedical text
• A technique for isolating differences between files
• A unifying taxonomy of pattern matching in degenerate strings and founder graphs
• Acronyms: identification, expansion and disambiguation
• Algorithms and complexity on indexing founder graphs
• Algorithms on Strings
• Algorithms on Strings, Trees and Sequences
• An algorithm for approximate membership checking with application to password security
• An Efficient Elastic-Degenerate Text Index? Not Likely
• Approximate pattern matching on elastic-degenerate text
• Comparing Degenerate Strings
• Comparing elastic-degenerate strings: algorithms, lower bounds, and applications
• Computational graph pangenomics: a tutorial on data structures and their applications
• Degenerate string comparison and applications
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Efficient pattern matching in elastic-degenerate strings
• Elastic founder graphs improved and enhanced
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Elastic-degenerate string matching with 1 error
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Faster Online Elastic Degenerate String Matching
• scientific article; zbMATH DE number 3984596 (Why is no real title available?)
• scientific article; zbMATH DE number 1958322 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• Incremental String Comparison
• Introduction to algorithms.
• Linear time construction of indexable founder block graphs
• On Indeterminate Strings Matching.
• On the complexity of k-SAT
• On the Complexity of String Matching for Graphs
• On-line pattern matching on similar texts
• Popular conjectures imply strong lower bounds for dynamic problems
• Quadratic conditional lower bounds for string problems and dynamic time warping
• Sparse regular expression matching
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Subcubic equivalences between path, matrix and triangle problems
• The complexity of satisfiability of small depth circuits
• The String-to-String Correction Problem
• Which problems have strongly exponential complexity?
• Which regular expression patterns are hard to match?

Cited in

(1)

• Faster approximate elastic-degenerate string matching. Part A

This page was built for publication: Elastic-degenerate string comparison

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