Constant delay traversal of grammar-compressed graphs with bounded rank

DOI10.1016/J.IC.2020.104520MaRDI QIDQ776844zbMATHOpenAlexWikidataFDO

Authors Sebastian Maneth, Fabian Peternek

Publication date 13 July 2020

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

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

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)

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.

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

Cites work

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

Cited in

(1)

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

Describes a project that uses

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)