Constant-time tree traversal and subtree equality check for grammar-compressed trees

DOI10.1007/s00453-017-0331-3zbMath1392.68185OpenAlexW2738674715MaRDI QIDQ724220

Sebastian Maneth, Carl Philipp Reh, Markus Lohrey

Publication date: 25 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0331-3

zbMATH Keywords

algorithms for compressed treesgrammar-compressed treestree straight-line programs

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Data structures (68P05)

Related Items (2)

Constant delay traversal of grammar-compressed graphs with bounded rank ⋮ Balancing straight-line programs for strings and trees

Uses Software

• TreeRePair

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• XML compression via directed acyclic graphs
• Parameter reduction and automata evaluation for grammar-compressed trees
• Using multiset discrimination to solve language processing problems without hashing
• The complexity of tree automata and XPath on grammar-compressed trees
• Automata for XML -- a survey
• Tree compression with top trees
• Fully Functional Static and Dynamic Succinct Trees
• Algorithmics on SLP-compressed strings: A survey
• Constructing Small Tree Grammars and Small Circuits for Formulas
• The Smallest Grammar Problem
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Algorithms on Strings, Trees and Sequences
• Random Access to Grammar-Compressed Strings and Trees
• Database Programming Languages

This page was built for publication: Constant-time tree traversal and subtree equality check for grammar-compressed trees