Hardness of comparing two run-length encoded strings

DOI10.1016/J.JCO.2010.03.003MaRDI QIDQ990818zbMATHOpenAlexFDO

Authors Kuan-Yu Chen, Ping-Hui Hsu, Kun-Mao Chao

Publication date 1 September 2010

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2010.03.003

zbMATH Keywords

run-length encodingsequence comparisoncompressed pattern matching

Mathematics Subject Classification ID

Bounds on codes (94B65)

Recommendations

• An algorithm for matching run-length coded strings
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
• Almost linear time computation of maximal repetitions in run length encoded strings
• Matching for run-length encoded strings
• Approximate matching of run-length compressed strings
• scientific article; zbMATH DE number 1786446
• Computing similarity of run-length encoded strings with affine gap penalty
• Parallel comparison of run-length-encoded strings on a linear systolic array

Cites work

• scientific article; zbMATH DE number 742992 (Why is no real title available?)
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Approximate matching of run-length compressed strings
• Edit distance for a run-length-encoded string and an uncompressed string
• Faster algorithms for string matching with k mismatches
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• From coding theory to efficient pattern matching
• Generalized String Matching
• Inplace run-length 2d compressed search.
• Matching for run-length encoded strings
• Matching patterns in strings subject to multi-linear transformations
• On a class of \(O(n^ 2)\) problems in computational geometry
• POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• Simple deterministic wildcard matching

Cited in

(6)

• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
• Efficient retrieval of approximate palindromes in a run-length encoded string
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Gel'fand-\(N\)-width in probabilistic setting
• Rényi entropy and pattern matching for run-length encoded sequences
• Approximation of functions on the sphere on a Sobolev space with a Gaussian measure in the probabilistic case setting

This page was built for publication: Hardness of comparing two run-length encoded strings

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