scientific article; zbMATH DE number 6027244

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.

zbMATH Keywords

straight-line programsedit distancecombinatorial pattern matchingdynamic programming acceleration via compression

Mathematics Subject Classification ID

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