A bisection algorithm for grammar-based compression of ordered trees

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.