Processing Compressed Texts: A Tractability Border

DOI10.1007/978-3-540-73437-6_24zbMath1138.68419OpenAlexW1486245824MaRDI QIDQ3506925

Yury Lifshits

Publication date: 17 June 2008

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73437-6_24

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items

Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts ⋮ Speeding up HMM decoding and training by exploiting sequence repetitions ⋮ Equality Testing of Compressed Strings ⋮ Edit Distance for Pushdown Automata ⋮ Congruence Closure of Compressed Terms in Polynomial Time ⋮ Linear-time text compression by longest-first substitution ⋮ Straight-line programs: a practical test (extended abstract) ⋮ The fully compressed subgroup membership problem ⋮ Unified compression-based acceleration of edit-distance computation ⋮ Fast equality test for straight-line compressed strings ⋮ Parameter reduction and automata evaluation for grammar-compressed trees ⋮ Compressed word problems in HNN-extensions and amalgamated products ⋮ An efficient algorithm to test square-freeness of strings compressed by straight-line programs ⋮ Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time ⋮ Compressed Membership in Automata with Compressed Labels ⋮ Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition ⋮ Isomorphism of Regular Trees and Words ⋮ Leaf languages and string compression ⋮ Boosting over non-deterministic ZDDs ⋮ Computing Longest Common Substring and All Palindromes from Compressed Strings ⋮ Detecting regularities on grammar-compressed strings ⋮ Efficient algorithms to compute compressed longest common substrings and compressed palindromes ⋮ THE INCLUSION PROBLEM OF CONTEXT-FREE LANGUAGES: SOME TRACTABLE CASES ⋮ Tracing compressed curves in triangulated surfaces ⋮ Unification with Singleton Tree Grammars ⋮ The Inclusion Problem of Context-Free Languages: Some Tractable Cases ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Fast distance multiplication of unit-Monge matrices

This page was built for publication: Processing Compressed Texts: A Tractability Border