Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
Authors:
- 1 January 2013
- book chapter
- Published by Springer Nature
- p. 247-258
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- Random Access to Grammar-Compressed Strings2011
- Unifying the Landscape of Cell-Probe Lower BoundsSIAM Journal on Computing, 2011
- Self-indexed Text Compression Using Straight-Line Programs2009
- The Smallest Grammar ProblemIEEE Transactions on Information Theory, 2005
- An information statistics approach to data stream and communication complexityJournal of Computer and System Sciences, 2004
- On data structures and asymmetric communication complexity1995
- On the distributional complexity of disjointnessTheoretical Computer Science, 1992
- Complexity classes in communication complexity theory1986
- Should Tables Be Sorted?Journal of the ACM, 1981
- On the Complexity of Finite SequencesIEEE Transactions on Information Theory, 1976