Conference paper · Book chapter
Tight bounds for top tree compression
In
Lecture Notes in Computer Science
—
2017, Volume 10508, pp. 97-102
Abstract
We consider compressing labeled, ordered and rooted trees using DAG compression and top tree compression. We show that there exists a family of trees such that the size of the DAG compression is always a logarithmic factor smaller than the size of the top tree compression (even for an alphabet of size 1).
The result settles an open problem from Bille et al. (Inform. and Comput., 2015).
| Language: | English |
|---|---|
| Publisher: | Springer |
| Year: | 2017 |
| Pages: | 97-102 |
| Proceedings: | 24th International Symposium on String Processing and Information Retrieval |
| Series: | Lecture Notes in Computer Science |
| Journal subtitle: | 24th International Symposium, Spire 2017, Palermo, Italy, September 26–29, 2017, Proceedings |
| ISBN: | 3319674277 , 3319674285 , 9783319674278 and 9783319674285 |
| ISSN: | 03029743 |
| Types: | Conference paper and Book chapter |
| DOI: | 10.1007/978-3-319-67428-5_9 |
| ORCIDs: | Bille, Philip , Gørtz, Inge Li , 0000-0002-3536-327X , 0000-0001-6928-0168 and 0000-0002-9830-3936 |
