Balancing Straight-Line Programs
| Autor: | Ganardi, Moses, Jeż, Artur, Lohrey, Markus |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 $\mathcal{O}(m)$, whose unique derivation tree has depth $\mathcal{O}(\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 $\mathcal{O}(\log n)$ with the cost of a constant multiplicative size increase. Here, $n$ refers to the size of the unfolding (or unravelling) of the circuit. Comment: An extended abstract of this paper appears in the Proceedings of FOCS 2019 |
| Databáze: | arXiv |
| Externí odkaz: |
|