The Smallest Grammar Problem

DOI10.1109/TIT.2005.850116zbMath1296.68086OpenAlexW2113004376WikidataQ29301656 ScholiaQ29301656MaRDI QIDQ3546682

Ding Liu, Rina Panigrahy, Eric Lehman, Manoj Prabhakaran, Amit Sahai, Abhi Shelat, Moses Charikar

Publication date: 21 December 2008

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tit.2005.850116

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Approximation algorithms (68W25)

Related Items (80)

Block graphs in practice ⋮ Comparison of LZ77-type parsings ⋮ UNIVERSAL CODING AND PREDICTION ON ERGODIC RANDOM POINTS ⋮ Upper bounds on distinct maximal (sub-)repetitions in compressed strings ⋮ Equality Testing of Compressed Strings ⋮ Compressed Tree Canonization ⋮ A separation between RLSLPs and LZ77 ⋮ Grammar-Based Tree Compression ⋮ Access, Rank, and Select in Grammar-compressed Strings ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Unnamed Item ⋮ An LMS-based grammar self-index with local consistency properties ⋮ On the approximation ratio of LZ-end to LZ77 ⋮ Finding the smallest binarization of a CFG is NP-hard ⋮ Self-indexed Text Compression Using Straight-Line Programs ⋮ The compressed word problem in relatively hyperbolic groups ⋮ Approximation of smallest linear tree grammar ⋮ The complexity of tree automata and XPath on grammar-compressed trees ⋮ Constructing small tree grammars and small circuits for formulas ⋮ Fingerprints in compressed strings ⋮ Grammar compressed sequences with rank/select support ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Straight-line programs: a practical test (extended abstract) ⋮ Compact q-gram profiling of compressed strings ⋮ Binary jumbled pattern matching on trees and tree-like structures ⋮ String Indexing with Compressed Patterns ⋮ A bisection algorithm for grammar-based compression of ordered trees ⋮ String search experimentation using massive data ⋮ Inductive synthesis of cover-grammars with the help of ant colony optimization ⋮ Balancing run-length straight-line programs ⋮ Searching for smallest grammars on large sequences and application to DNA ⋮ A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct ⋮ Time-space trade-offs for Lempel-Ziv compressed indexing ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ Random access in persistent strings and segment selection ⋮ Improved approximation algorithms for minimum AND-circuits problem via \(k\)-set cover ⋮ Lower bounds for context-free grammars ⋮ A \textit{really} simple approximation of smallest grammar ⋮ Knapsack in graph groups ⋮ On the compressibility of finite languages and formal proofs ⋮ Parameter reduction and automata evaluation for grammar-compressed trees ⋮ Unnamed Item ⋮ Block trees ⋮ Universal compressed text indexing ⋮ Cadences in grammar-compressed strings ⋮ The smallest grammar problem as constituents choice and minimal grammar parsing ⋮ On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation ⋮ A Self-index on Block Trees ⋮ Approximation of grammar-based compression via recompression ⋮ Tree compression using string grammars ⋮ Compressed subsequence matching and packed tree coloring ⋮ Functional programs as compressed data ⋮ The complexity of compressed membership problems for finite automata ⋮ Staged self-assembly and polyomino context-free grammars ⋮ Variable-length coding of two-sided asymptotically mean stationary measures ⋮ Compaction of Church numerals ⋮ Leaf languages and string compression ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Grammar-based compression of unranked trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ LZ77 computation based on the run-length encoded BWT ⋮ Constant-time tree traversal and subtree equality check for grammar-compressed trees ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Learning grammars for architecture-specific facade parsing ⋮ Compressed range minimum queries ⋮ On the Value of Multiple Read/Write Streams for Data Compression ⋮ Approximability of minimum AND-circuits ⋮ Finger search in grammar-compressed strings ⋮ Compressibility of Finite Languages by Grammars ⋮ Random Access to High-Order Entropy Compressed Text ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Approximate pattern matching in LZ77-compressed texts ⋮ Balancing straight-line programs for strings and trees ⋮ Excess entropy in natural language: Present state and perspectives ⋮ Tree compression with top trees ⋮ Lazy Lempel-Ziv Factorization Algorithms ⋮ Lyndon factorization of grammar compressed texts revisited ⋮ Compression techniques in group theory

This page was built for publication: The Smallest Grammar Problem