Nöth, Eric: Analysis of grammar-based tree compressionAnalyse grammatik-basierter Baumkompression. 2016
Inhalt
- Contents
- Introduction
- Preliminaries
- The average-case size of the DAG
- Generating functions and the Catalan numbers
- Exact counting
- Complex analysis and singularity analysis
- Proof of the main theorem
- Extensions
- On proving the main result by Mellin transform
- Open problems related to DAGs
- The hybrid DAG and worst-case sizes
- The construction
- Comparison of the worst-case sizes of DAG, BDAG and HDAG
- The average size of the HDAG
- DAG compression using string grammars
- Tree compression using string grammars
- Trees as preorder traversals
- Checking whether an SLP produces a tree
- Comparison with other grammar-based tree representations
- Experiments
- Algorithmic Problems
- Accelerated computation by compression in term rewriting
- Term Rewriting
- Term Compression with TreeRePair
- Compression and the DP-transformation
- Experiments
- Discussion
- Conclusion and final remarks
- Bibliography