Inhalt

•  
   Contents
•  
   Introduction
•  
  Preliminaries
•  
   Trees
•  
   The FCNS-encoding
•  
   The minimal directed acyclic graph
•  
  Grammars
•  
   SLP grammars
•  
   TSLP grammars
•  
   The average-case size of the DAG
•  
   Generating functions and the Catalan numbers
•  
   Exact counting
•  
   Complex analysis and singularity analysis
•  
   Complex analysis
•  
   The standard function scale
•  
   Singularity transfer
•  
   Proof of the main theorem
•  
   Extensions
•  
   Exact counting
•  
   Asymptotic results
•  
   On proving the main result by Mellin transform
•  
  Open problems related to DAGs
•  
   Variance
•  
   Unordered trees
•  
   The average size of the DAG of regular tree languages
•  
  The hybrid DAG and worst-case sizes
•  
   The construction
•  
  Comparison of the worst-case sizes of DAG, BDAG and HDAG
•  
   The number of nodes
•  
   The number of edges
•  
   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
•  
   Traversal SLPs versus TSLPs
•  
   Traversal SLPs versus balanced parenthesis representation
•  
  Experiments
•  
   Corpora
•  
   Experiment Setup
•  
   Comparison
•  
  Algorithmic Problems
•  
   Subtree equality check
•  
   Tree Automata
•  
   Tree Navigation
•  
   Accelerated computation by compression in term rewriting
•  
   Term Rewriting
•  
   Termination and matrix interpretations
•  
   Cost of terms
•  
  Term Compression with TreeRePair
•  
   TreeRePair
•  
   Minimizing the matrix multiplication cost
•  
   Compression and the DP-transformation
•  
   Experiments
•  
   Discussion
•  
   Conclusion and final remarks
•  
   Bibliography