nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Grammar-Based Compression of Unranked Trees

verfasst von : Adrià Gascón, Markus Lohrey, Sebastian Maneth, Carl Philipp Reh, Kurt Sieber

Erschienen in: Computer Science – Theory and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Maximum Colorful Cycles in Vertex-Colored Graphs

Nächstes Kapitel Complement for Two-Way Alternating Automata

Abiteboul, S., Bourhis, P., Vianu, V.: Highly expressive query languages for unordered data trees. Theor. Comput. Syst. 57(4), 927–966 (2015)MathSciNetCrossRefMATH

Bille, P., Gørtz, I.L., Landau, G.M., Weimann, O.: Tree compression with top trees. Inf. Comput. 243, 166–177 (2015)MathSciNetCrossRefMATH

Boiret, A., Hugot, V., Niehren, J., Treinen, R.: Logics for unordered trees with data constraints on siblings. In: Dediu, A.-H., Formenti, E., Martín-Vide, C., Truthe, B. (eds.) LATA 2015. LNCS, vol. 8977, pp. 175–187. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-15579-1_13CrossRefMATH

Bojańczyk, M., Walukiewicz, I.: Forest algebras. In: Proceedings of Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas], Texts in Logic and Games, vol. 2, pp. 107–132. Amsterdam University Press (2008)

Boneva, I., Ciucanu, R., Staworko, S.: Schemas for unordered XML on a DIME. Theory Comput. Syst. 57(2), 337–376 (2015)MathSciNetCrossRefMATH

Busatto, G., Lohrey, M., Maneth, S.: Efficient memory representation of XML document trees. Inf. Syst. 33(4–5), 456–474 (2008)CrossRefMATH

Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Löding, C., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications. http://www.grappa.univ-lille3.fr/tata (2007)

Creus, C., Gascón, A., Godoy, G.: One-context unification with STG-compressed terms is in NP. In: Proceedings of RTA 2012, LIPIcs 15, pp. 149–164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Dudek, B., Gawrychowski, P.: Slowing down top trees for better worst-case bounds (2018). https://arxiv.org/abs/1801.01059

10.

Gascón, A., Godoy, G., Schmidt-Schauß, M.: Unification and matching on compressed terms. ACM Trans. Comput. Logic 12(4), 26:1–26:37 (2011)MathSciNetCrossRefMATH

11.

Gascón, A., Lohrey, M., Maneth, S., Reh, P., Sieber, K.: Grammar-based compression of unranked trees (2018). https://arxiv.org/abs/1802.05490CrossRef

12.

Hübschle-Schneider, L., Raman, R.: Tree compression with top trees revisited. In: Bampis, E. (ed.) SEA 2015. LNCS, vol. 9125, pp. 15–27. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-20086-6_2CrossRef

13.

Jeż, A.: Context unification is in PSPACE. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 244–255. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43951-7_21CrossRef

14.

Lohrey, M.: Algorithmics on SLP-compressed strings: a survey. Groups Complex. Cryptol. 4(2), 241–299 (2012)MathSciNetMATH

15.

Lohrey, M., Maneth, S., Mennicke, R.: XML tree structure compression using RePair. Inf. Syst. 38(8), 1150–1167 (2013)CrossRef

16.

Lohrey, M., Maneth, S., Peternek, F.: Compressed tree canonization. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 337–349. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47666-6_27CrossRef

17.

Lohrey, M., Maneth, S., Reh, C.P.: Compression of unordered XML trees. In: Proceedings of ICDT 2017, LIPIcs 68, pp. 18:1–18:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

18.

Lohrey, M., Maneth, S., Schmidt-Schauß, M.: Parameter reduction and automata evaluation for grammar-compressed trees. J. Comput. Syst. Sci. 78(5), 1651–1669 (2012)MathSciNetCrossRefMATH

19.

Lohrey, M., Reh, P., Sieber, K.: Optimal top dag construction (2017). https://arxiv.org/abs/1712.05822

20.

Sundaram, S., Madria, S.K.: A change detection system for unordered XML data using a relational model. Data Knowl. Eng. 72, 257–284 (2012)CrossRef

Titel: Grammar-Based Compression of Unranked Trees
verfasst von: Adrià Gascón
Markus Lohrey
Sebastian Maneth
Carl Philipp Reh
Kurt Sieber
Verlag: Springer International Publishing
Buch: Computer Science – Theory and Applications
Print ISBN: 978-3-319-90529-7

Electronic ISBN: 978-3-319-90530-3

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-90530-3_11

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"