Balancing Straight-line Programs

DOI10.1145/3457389MaRDI QIDQ5056417zbMATH OpenOpenAlexFDO

Authors Moses Ganardi, Artur Jeż, Markus Lohrey

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.03568

zbMATH Keywords

balancinggrammar-based compressionrandom access problemstraight-line programs

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)

Abstract: It is shown that a context-free grammar of size $m$ that produces a single string $w$ (such a grammar is also called a string straight-line program) can be transformed in linear time into a context-free grammar for $w$ of size $mathcalO(m)$, whose unique derivation tree has depth $mathcalO(log|w|)$. This solves an open problem in the area of grammar-based compression. Similar results are shown for two formalism for grammar-based tree compression: top dags and forest straight-line programs. These balancing results are all deduced from a single meta theorem stating that the depth of an algebraic circuit over an algebra with a certain finite base property can be reduced to $mathcalO(logn)$ with the cost of a constant multiplicative size increase. Here, $n$ refers to the size of the unfolding (or unravelling) of the circuit.

Recommendations

• Constructing small tree grammars and small circuits for formulas
• Constructing small tree grammars and small circuits for formulas
• A universal tree balancing theorem
• Straight-line programs: a practical test (extended abstract)

Cited in

(21)

• Finding optimal line balances with OptPack
• Balancing straight-line programs for strings and trees
• Constructing small tree grammars and small circuits for formulas
• A universal tree balancing theorem
• Balancing run-length straight-line programs
• Random access in persistent strings and segment selection
• Iterated straight-line programs
• Space-efficient conversions from SLPs
• Wheeler maps
• Internal pattern matching queries in a text and applications
• Bat-LZ out of hell
• Repetitiveness measures based on string morphisms
• Generalized straight-line programs
• How to find long maximal exact matches and ignore short ones
• Computing string covers in sublinear time
• Space-efficient SLP encoding for O( N)-time random access
• A formal language perspective on factorized representations
• Counting on general run-length grammars
• Pattern matching on run-length grammar-compressed strings in linear time
• FO-query enumeration over SLP-compressed structures of bounded degree
• Constant delay traversal of grammar-compressed graphs with bounded rank

This page was built for publication: Balancing Straight-line Programs

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