Back to Search
Start Over
Grammar-Based Compression of Unranked Trees.
- Source :
-
Theory of Computing Systems . Jan2020, Vol. 64 Issue 1, p141-176. 36p. - Publication Year :
- 2020
-
Abstract
- We introduce forest straight-line programs (FSLPs for short) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and generalize tree straight-line programs. We compare the succinctness of FSLPs with two other compression schemes for unranked trees: top dags and tree straight-line programs of first-child/next sibling encodings. Efficient translations between these formalisms are provided. Finally, we show that equality of unranked trees in the setting where certain symbols are associative and/or commutative can be tested in polynomial time. This generalizes previous results for testing isomorphism of compressed unordered ranked trees. An extended abstract of this paper appeared in Gascóon et al. (2018). [ABSTRACT FROM AUTHOR]
- Subjects :
- *POLYNOMIAL time algorithms
*TREES
*IMAGE compression
Subjects
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 64
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 140956331
- Full Text :
- https://doi.org/10.1007/s00224-019-09942-y