Constant delay traversal of grammar-compressed graphs with bounded rank

DOI10.1016/J.IC.2020.104520zbMATH Open1446.68044arXiv1907.10444OpenAlexW3000377615WikidataQ126345716 ScholiaQ126345716MaRDI QIDQ776844FDOQ776844

Authors: Sebastian Maneth, Fabian Peternek 

Publication date: 13 July 2020

Published in: Information and Computation (Search for Journal in Brave)

Abstract: We present a pointer-based data structure for constant time traversal of the edges of an edge-labeled (alphabet $Sigma$) directed hypergraph (a graph where edges can be incident to more than two vertices, and the incident vertices are ordered) given as hyperedge-replacement grammar $G$. It is assumed that the grammar has a fixed rank $kappa$ (maximal number of vertices connected to a nonterminal hyperedge) and that each vertex of the represented graph is incident to at most one $sigma$-edge per direction ($sigmainSigma$). Precomputing the data structure needs $O(|G||Sigma|kapparh)$ space and $O(|G||Sigma|kappar{h}^2)$ time, where $h$ is the height of the derivation tree of $G$ and $r$ is the maximal rank of a terminal edge occurring in the grammar.

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

Recommendations

• Constant-time tree traversal and subtree equality check for grammar-compressed trees
• Navigating Forest Straight-Line Programs in Constant Time
• Access, rank, and select in grammar-compressed strings
• Between a rock and a hard place -- uniform parsing for hyperedge replacement DAG grammars
• Random access to grammar-compressed strings and trees

Mathematics Subject Classification ID

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

Cites Work

• Algorithms on Strings, Trees and Sequences
• Hyperedge replacement: grammars and languages
• Fully functional static and dynamic succinct trees
• Succinct Trees in Practice
• The level ancestor problem simplified
• Algorithmics on SLP-compressed strings: a survey
• Parameter reduction and automata evaluation for grammar-compressed trees
• Handbook of Graph Grammars and Computing by Graph Transformation
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Tree compression with top trees
• Approximation of smallest linear tree grammar
• Grammar-Based Tree Compression
• Random access to grammar-compressed strings and trees
• Constant-time tree traversal and subtree equality check for grammar-compressed trees
• Balancing Straight-line Programs

Cited In (1)

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

Uses Software

• TreeRePair

This page was built for publication: Constant delay traversal of grammar-compressed graphs with bounded rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776844)