Processing Compressed Texts: A Tractability Border

DOI10.1007/978-3-540-73437-6_24MaRDI QIDQ3506925zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1490000
• Pattern matching in compressed texts
• Querying and Embedding Compressed Texts
• Faster subsequence recognition in compressed strings
• Efficient algorithms for Lempel-Ziv encoding

Cited in

(30)

• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Linear-time text compression by longest-first substitution
• Unified compression-based acceleration of edit-distance computation
• Fast distance multiplication of unit-Monge matrices
• Detecting regularities on grammar-compressed strings
• Computing \(q\)-gram non-overlapping frequencies on SLP compressed texts
• Compressed membership in automata with compressed labels
• Towards approximate matching in compressed strings: local subsequence recognition
• Isomorphism of regular trees and words
• The inclusion problem of context-free languages: some tractable cases
• Congruence closure of compressed terms in polynomial time
• Equality Testing of Compressed Strings
• Edit distance for pushdown automata
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• Unification with Singleton Tree Grammars
• The Inclusion Problem of Context-Free Languages: Some Tractable Cases
• Straight-line programs: a practical test (extended abstract)
• Fast equality test for straight-line compressed strings
• Parameter reduction and automata evaluation for grammar-compressed trees
• An efficient algorithm to test square-freeness of strings compressed by straight-line programs
• Random access to grammar-compressed strings and trees
• Computing Longest Common Substring and All Palindromes from Compressed Strings
• Leaf languages and string compression
• Querying and Embedding Compressed Texts
• Boosting over non-deterministic ZDDs
• Tracing compressed curves in triangulated surfaces
• The fully compressed subgroup membership problem
• Compressed word problems in HNN-extensions and amalgamated products
• Extended formulations via decision diagrams
• Speeding up HMM decoding and training by exploiting sequence repetitions

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

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