XML compression via directed acyclic graphs

DOI10.1007/s00224-014-9544-xzbMath1352.68079arXiv1309.5927OpenAlexW2022891963MaRDI QIDQ269349

Markus Lohrey, Mireille Bousquet-Mélou, Sebastian Maneth, Eric Noeth

Publication date: 18 April 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1309.5927

zbMATH Keywords

XMLdirected acyclic graphtree compression

Mathematics Subject Classification ID

Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Directed graphs (digraphs), tournaments (05C20)

Related Items (12)

Approximation of smallest linear tree grammar ⋮ Constructing small tree grammars and small circuits for formulas ⋮ Compaction for two models of logarithmic‐depth trees: Analysis and experiments ⋮ Simplifications of Uniform Expressions Specified by Systems ⋮ Unnamed Item ⋮ A bijection of plane increasing trees with relaxed binary trees of right height at most one ⋮ Tree compression using string grammars ⋮ Compacted binary trees admit a stretched exponential ⋮ From tree automata to string automata minimization ⋮ Constant-time tree traversal and subtree equality check for grammar-compressed trees ⋮ Asymptotic enumeration of compacted binary trees of bounded right height ⋮ Distinct fringe subtrees in random trees

Uses Software

• XMill
• TreeRePair

Cites Work

• Parameter reduction and automata evaluation for grammar-compressed trees
• The complexity of tree automata and XPath on grammar-compressed trees
• Automata for XML -- a survey
• Enumerations of ordered trees
• The average height of binary trees and other simple trees
• Algorithmics on SLP-compressed strings: A survey
• On programming of arithmetic operations
• Singularity Analysis of Generating Functions
• Variations on the Common Subexpression Problem
• The rotation correspondence is asymptotically a dilatation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: XML compression via directed acyclic graphs