Equality Testing of Compressed Strings

DOI10.1007/978-3-319-23660-5_2zbMath1375.68233MaRDI QIDQ3449353

Markus Lohrey

Publication date: 4 November 2015

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

Full work available at URL: https://doi.org/10.1007/978-3-319-23660-5_2

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W32: Algorithms on strings

Cites Work

• A Mathematical Theory of Communication
• Fast equality test for straight-line compressed strings
• Succinct circuit representations and leaf language classes are basically the same concept
• Succinct representation, leaf languages, and projection reductions
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• On the complexity of pattern matching for highly compressed two-dimensional texts.
• Faster Fully Compressed Pattern Matching by Recompression
• Algorithmics on SLP-compressed strings: A survey
• Parallel Identity Testing for Skew Circuits with Big Powers and Applications
• Succinct representations of graphs
• Primality and identity testing via Chinese remaindering
• Processing Compressed Texts: A Tractability Border
• The Smallest Grammar Problem
• The parallel complexity of exponentiating polynomials over finite fields
• The complexity of searching succinctly represented graphs
• A note on succinct representations of graphs
• Efficient algorithms for Lempel-Ziv encoding
• Uniqueness Theorems for Periodic Functions
• The Compressed Word Problem for Groups
• Introduction to Lie Algebras and Representation Theory
• Querying and Embedding Compressed Texts
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item