Equality Testing of Compressed Strings

DOI10.1007/978-3-319-23660-5_2zbMATH Open1375.68233OpenAlexW2176419491MaRDI QIDQ3449353FDOQ3449353

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

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Cites Work

• A Mathematical Theory of Communication
• Title not available (Why is that?)
• Approximation of smallest linear tree grammar
• Title not available (Why is that?)
• Title not available (Why is that?)
• Introduction to Lie Algebras and Representation Theory
• Algorithmics on SLP-compressed strings: a survey
• Title not available (Why is that?)
• Succinct representation, leaf languages, and projection reductions
• Succinct representations of graphs
• A note on succinct representations of graphs
• Succinct circuit representations and leaf language classes are basically the same concept
• Uniqueness Theorems for Periodic Functions
• Derandomizing polynomial identity tests means proving circuit lower bounds
• The Smallest Grammar Problem
• Processing Compressed Texts: A Tractability Border
• Primality and identity testing via Chinese remaindering
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Efficient algorithms for Lempel-Ziv encoding
• On the complexity of pattern matching for highly compressed two-dimensional texts.
• Fast equality test for straight-line compressed strings
• Querying and Embedding Compressed Texts
• The parallel complexity of exponentiating polynomials over finite fields
• The complexity of searching succinctly represented graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Compressed Word Problem for Groups
• Parallel identity testing for skew circuits with big powers and applications

Cited In (1)

• Comparing Degenerate Strings

This page was built for publication: Equality Testing of Compressed Strings

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