摘要

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(n(5/6)). We also show that the grammar and algorithm can be modified for unordered trees of bounded degree.

  • 出版日期2010-9-15