Elastic-Degenerate String Matching via Fast Matrix Multiplication
DOI10.1137/20M1368033OpenAlexW3158236668WikidataQ114074153 ScholiaQ114074153MaRDI QIDQ5864665FDOQ5864665
Authors: Giulia Bernardini, Paweł Gawrychowski, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone 
Publication date: 8 June 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1905.02298
Recommendations
- Even faster elastic-degenerate string matching via fast matrix multiplication
- Faster Online Elastic Degenerate String Matching
- A new approach to pattern matching in degenerate DNA/RNA sequences and distributed pattern matching
- Fast and linear-time string matching algorithms based on the distances of \(q\)-gram occurrences
- Efficient string matching with k mismatches
fast Fourier transformmatrix multiplicationpattern matchingstring algorithmselastic-degenerate string
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32) General topics in the theory of algorithms (68W01)
Cites Work
- Powers of tensors and fast matrix multiplication
- Two-way string-matching
- An Algorithm for the Machine Calculation of Complex Fourier Series
- A data structure for dynamic trees
- Efficient determination of the transitive closure of a directed graph
- Factorizing words over an ordered alphabet
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Multiplying matrices faster than coppersmith-winograd
- Computing dominances in \(E^ n\)
- Constructing Efficient Dictionaries in Close to Sorting Time
- The complexity of satisfiability of small depth circuits
- Fast Pattern Matching in Strings
- Algorithms – ESA 2004
- Uniqueness Theorems for Periodic Functions
- General context-free recognition in less than cubic time
- Fast context-free grammar parsing requires fast Boolean matrix multiplication
- Verifying candidate matches in sparse and wildcard matching
- Generalized String Matching
- Multidimensional binary search trees used for associative searching
- Finding a Minimum Circuit in a Graph
- Faster algorithms for string matching with k mismatches
- Internal pattern matching queries in a text and applications
- Algorithms on Strings
- Simple deterministic wildcard matching
- Title not available (Why is that?)
- Fast pattern-matching on indeterminate strings
- Regularity Lemmas and Combinatorial Algorithms
- Title not available (Why is that?)
- Speeding up the four Russians algorithm by about one more logarithmic factor
- Lossless filter for multiple repetitions with Hamming distance
- NR-grep: A fast and flexible pattern-matching tool
- Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
- Finding a maximum weight triangle in n 3-Δ time, with applications
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- If the current clique algorithms are optimal, so is Valiant's parser
- Even faster elastic-degenerate string matching via fast matrix multiplication
- On-line pattern matching on similar texts
- Faster Online Elastic Degenerate String Matching
- Linear time construction of indexable founder block graphs
- Approximate pattern matching on elastic-degenerate text
- Hardness of RNA folding problem with four symbols
- Title not available (Why is that?)
- Towards unified approximate pattern matching for Hamming and \(L_1\) distance
- Pattern matching on elastic-degenerate text with errors
- On hardness of several string indexing problems
- Color-distance oracles and snippets
- Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
- Comparing Degenerate Strings
Cited In (6)
- Approximate pattern matching on elastic-degenerate text
- Title not available (Why is that?)
- Even faster elastic-degenerate string matching via fast matrix multiplication
- Elastic-degenerate string matching with 1 error
- Elastic-degenerate string matching with 1 error or mismatch
- Faster Online Elastic Degenerate String Matching
Uses Software
This page was built for publication: Elastic-Degenerate String Matching via Fast Matrix Multiplication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5864665)
