Grammar-based compression of unranked trees

DOI10.1007/978-3-319-90530-3_11zbMath1434.68128arXiv1802.05490OpenAlexW2963905622MaRDI QIDQ5915574

Sebastian Maneth, Adrià Gascón, Markus Lohrey, Carl Philipp Reh, Kurt Sieber

Publication date: 28 November 2018

Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

equality testingforestgrammar-based tree compressiontop dags

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

Size-optimal top dag compression ⋮ Grammar-based compression of unranked trees ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Balancing straight-line programs for strings and trees

Uses Software

• TreeRePair

Cites Work

• Unnamed Item
• Unnamed Item
• Highly expressive query languages for unordered data trees
• Parameter reduction and automata evaluation for grammar-compressed trees
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• Schemas for unordered XML on a DIME
• Tree compression with top trees
• Size-optimal top dag compression
• Logics for Unordered Trees with Data Constraints on Siblings
• Faster Fully Compressed Pattern Matching by Recompression
• Algorithmics on SLP-compressed strings: A survey
• Unification and matching on compressed terms
• Compression of Unordered XML Trees
• Compressed Tree Canonization
• Grammar-Based Tree Compression
• The Smallest Grammar Problem
• Balancing Straight-line Programs
• One-context Unification with STG-Compressed Terms is in NP
• Slowing Down Top Trees for Better Worst-Case Compression
• Context Unification is in PSPACE
• Computational Complexity
• Grammar-based compression of unranked trees