The Library
Grammar-based compression of unranked trees
Tools
Tools
Tools
Gascon, Adrià, Lohrey, Markus, Maneth, Sebastian, Reh, Carl Philipp and Sieber, Kurt (2018) Grammar-based compression of unranked trees. In: International Computer Science Symposium in Russia, Moscow, Russia, 6-10 Jun 2018, 10846 pp. 118-131. ISBN 9783319905297. doi:10.1007/978-3-319-90530-3_11
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: https://doi.org/10.1007/978-3-319-90530-3_11
Abstract
We introduce forest straight-line programs (FSLPs) 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 or commutative can be tested in polynomial time. This generalizes previous results for testing isomorphism of compressed unordered ranked trees.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Series Name: | Lecture Notes in Computer Science | ||||||
| Publisher: | Springer | ||||||
| Place of Publication: | Cham | ||||||
| ISBN: | 9783319905297 | ||||||
| Book Title: | Computer Science – Theory and Applications. CSR 2018 | ||||||
| Editor: | Fomin , F. and Podolskii , V. | ||||||
| Official Date: | 25 April 2018 | ||||||
| Dates: |
|
||||||
| Volume: | 10846 | ||||||
| Page Range: | pp. 118-131 | ||||||
| DOI: | 10.1007/978-3-319-90530-3_11 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | International Computer Science Symposium in Russia | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Moscow, Russia | ||||||
| Date(s) of Event: | 6-10 Jun 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
