| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427508 | Information Processing Letters | 2010 | 6 Pages |
Abstract
In this paper, we consider grammar-based compression for rooted ordered trees. For that purpose, we define an elementary ordered tree grammar (EOTG) by extending CFG, and then present a polynomial time algorithm which approximates the smallest EOTG within a factor of O(n5/6). We also show that the grammar and algorithm can be modified for unordered trees of bounded degree.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
