Querying and Embedding Compressed Texts

DOI10.1007/11821069_59MaRDI QIDQ5756685zbMATH OpenOpenAlexFDO

Authors Yury Lifshits, Markus Lohrey

Publication date 5 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11821069_59

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Processing Compressed Texts: A Tractability Border
• scientific article; zbMATH DE number 1490000
• Algorithmics on SLP-compressed strings: a survey
• scientific article; zbMATH DE number 1408351
• Compressed membership problems for regular expressions and hierarchical automata

Cited in

(17)

• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Certain query answering on compressed string patterns: from streams to hyperstreams
• Unified compression-based acceleration of edit-distance computation
• The complexity of compressed membership problems for finite automata
• Fast distance multiplication of unit-Monge matrices
• Compressed membership in automata with compressed labels
• Towards approximate matching in compressed strings: local subsequence recognition
• Faster subsequence and don't-care pattern matching on compressed texts
• Equality Testing of Compressed Strings
• Processing Compressed Texts: A Tractability Border
• Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
• Computing Longest Common Substring and All Palindromes from Compressed Strings
• Leaf languages and string compression
• Parity games on temporal graphs
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• Doubly-periodic string comparison
• Faster subsequence recognition in compressed strings

This page was built for publication: Querying and Embedding Compressed Texts

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