scientific article; zbMATH DE number 6027244
From MaRDI portal
Publication:5390005
DOI10.4230/LIPIcs.STACS.2009.1804zbMath1236.68308MaRDI QIDQ5390005
Danny Hermelin, Oren Weimann, Gad M. Landau, Shir Landau
Publication date: 24 April 2012
Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_6907.html
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
straight-line programsedit distancecombinatorial pattern matchingdynamic programming acceleration via compression
Dynamic programming (90C39) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)
Related Items
Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts ⋮ Linear-time text compression by longest-first substitution ⋮ Unified compression-based acceleration of edit-distance computation ⋮ A fully compressed algorithm for computing the edit distance of run-length encoded strings ⋮ Generalized substring compression ⋮ Efficient all path score computations on grid graphs ⋮ Edit distance with block deletions ⋮ Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition ⋮ Faster Subsequence and Don’t-Care Pattern Matching on Compressed Texts ⋮ On almost Monge all scores matrices ⋮ Boosting over non-deterministic ZDDs ⋮ A faster algorithm for the computation of string convolutions using LZ78 parsing ⋮ A Space-Optimal Grammar Compression. ⋮ Random Access to Grammar-Compressed Strings and Trees