# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Approximation of Smallest Linear Tree Grammar

##### External Resource

http://drops.dagstuhl.de/opus/volltexte/2014/4478/

(Any fulltext)

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Jeż, A., & Lohrey, M. (2014). Approximation of Smallest Linear Tree Grammar. In
E. W. Mayr, & N. Portier (*31st International Symposium
on Theoretical Aspects of Computer Science* (pp. 445-457). Wadern: Schloss Dagstuhl. doi:10.4230/LIPIcs.STACS.2014.445.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-55A2-1

##### Abstract

A simple linear-time algorithm
for constructing a linear
context-free tree grammar of size O(r^2 g łog n)
for a given input tree T of size n is presented, where g is the size of
a minimal linear context-free tree grammar for T, and r is the maximal rank
of symbols in T (which is a constant in many applications). This is the first
example of a grammar-based tree compression algorithm with an
approximation ratio polynomial in g. The analysis of the algorithm uses an
extension of the recompression technique
(used in the context of grammar-based string compression)
from strings to trees.