Reh, Carl Philipp: Algorithmic aspects of grammar-compressed trees. 2019
Inhalt
- Zusammenfassung (English)
- Zusammenfassung (Deutsch)
- Contents
- 1. Introduction
- 2. Algebras and SLPs
- 3. Normal form SLPs
- 4. Navigation
- 4.1 Navigating SSLPs
- 4.2 Navigating TSLPs
- 4.3 Navigating FSLPs
- 4.4 Subtree equality check for trees
- 4.5 Subtree equality check for forests
- 5. Relative succinctness
- 6. Testing equality modulo associativity and commutativity
- 7. Unordered forests
- 7.1 Lower Bounds for nodes/edges of DAGs
- 7.2 Upper Bound for edges of DAGs
- 7.3 Upper Bound for nodes of DAGs
- 7.4 FSLPs for unordered forests
- 7.5 TSLPs for unordered trees
- 7.6 Experimental Results
- 8. Evaluating Automata
- 9. Optimal worst-case compression
- 10. Future Work
- Bibliography
- Publications