Back to Search
Start Over
Approximation of smallest linear tree grammar.
- Source :
-
Information & Computation . Dec2016, Vol. 251, p215-251. 37p. - Publication Year :
- 2016
-
Abstract
- A simple linear-time algorithm for constructing a linear context-free tree grammar of size O ( r g + r g log ( n / r g ) ) 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 a good, i.e. logarithmic in terms of the size of the input tree, approximation ratio. The analysis of the algorithm uses an extension of the recompression technique from strings to trees. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08905401
- Volume :
- 251
- Database :
- Academic Search Index
- Journal :
- Information & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 119418556
- Full Text :
- https://doi.org/10.1016/j.ic.2016.09.007