pith. sign in

arxiv: 1907.10444 · v1 · pith:IUWBVQ2Pnew · submitted 2019-07-24 · 💻 cs.DS

Constant Delay Traversal of Grammar-Compressed Graphs with Bounded Rank

Sebastian Maneth , Fabian Peternek This is my paper

Pith reviewed 2026-05-24 16:39 UTC · model grok-4.3

classification 💻 cs.DS
keywords grammar compressionhyperedge replacementconstant time traversaldata structureshypergraphspointer based structuresbounded rank
0
0 comments X

The pith

A pointer-based data structure supports constant-time traversal of edges in hypergraphs given by bounded-rank hyperedge-replacement grammars.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to build a pointer-based data structure that lets you move from one edge to the next in a hypergraph in constant time, even when the hypergraph is given only as a compact grammar. This matters because the actual graph can be exponentially larger than the grammar, so expanding it first would be impractical for many applications. The method works when the grammar's rank is fixed and each vertex has at most one edge of each label in each direction. Precomputation time and space depend on the grammar size and the derivation tree height. If the claim holds, many graph algorithms that rely on edge traversal can run directly on the compressed form.

Core claim

The authors present a pointer-based data structure for constant time traversal of the edges of an edge-labeled directed hypergraph given as a hyperedge-replacement grammar with fixed rank, assuming each vertex is incident to at most one edge per label and direction. The data structure is precomputed in time and space polynomial in the grammar size, the rank, the maximum terminal rank, and the square of the derivation height.

What carries the argument

Pointer-based data structure that encodes next-edge pointers derived from the grammar productions.

If this is right

  • Traversal of the represented hypergraph can be performed without expanding it to full size.
  • Query time for the next edge is independent of the size of the grammar or the expanded graph.
  • The approach applies to directed edge-labeled hypergraphs where edges connect ordered tuples of vertices.
  • Space usage remains linear in the size of the input grammar times bounded factors.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar techniques might apply to other forms of graph compression beyond hyperedge replacement if boundedness conditions hold.
  • This enables efficient simulation of graph algorithms on implicitly defined large structures such as networks from biology or software.
  • Relaxing the uniqueness assumption on edges would likely require additional indexing structures to maintain constant delay.

Load-bearing premise

The grammar has bounded rank and each vertex has at most one incident edge per label and direction.

What would settle it

Build the data structure for a small qualifying grammar, then time a long sequence of successive edge traversals and check whether total time stays linear in the number of steps with a fixed per-step cost.

Figures

Figures reproduced from arXiv: 1907.10444 by Fabian Peternek, Sebastian Maneth.

Figure 1
Figure 1. Figure 1: Example of a drawing of a hypergraph with three vertices (two of which external) and three edges. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example of an edge replacement. Let g be a graph with a nonterminal edge e. A derivation step is defined as g ⇒ h if there exist a nonterminal edge e in g and a rule lab(e) → g 0 such that h = g[e/g0 ]. A derivation g ⇒∗ h consists of any number of derivation steps and we define the language of G as L(G) = {g ∈ HGR(Σ) | S ⇒∗ g}. Remark. This grammar formalism may be unfamiliar to some readers. We therefore… view at source ↗
Figure 3
Figure 3. Figure 3: HR grammar generating graphs representing the string language [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: One possible derivation of the HR grammar given in Figure 3. The resulting graph represents the string [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: An SL HR grammar (left), and it’s derivation tree (right). Light gray lines indicate for every external vertex, the [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The graph represented by the grammar given on the left of Figure 5. Vertices are colored to show their origin within [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Illustration of the traverse-mapping grammar. For a nonterminal A and a vertex x in rhs(A) the mapping traversek,l(A, x, σ) intuitively points us to the vertex y within a node label of the derivation tree dt(A) such that the vertices represented by x and y in val(A) are σ-k-l-neighbors. In our example the mapping traverse1,2(S, 1, a) points towards the vertex 1 in the node u4 of dt(S). Note that the arrow … view at source ↗
Figure 8
Figure 8. Figure 8: Part of the derivation tree from Figure 5 and the full graph with added annotations about 3 traversal steps. [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Grammar where every traversal step corresponds to a jump between the root and a leaf in the derivation tree. [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Branch of a derivation tree (left) and two tableaux, each representing parts of the branch. [PITH_FULL_IMAGE:figures/full_fig_p014_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Concatenating the pointers of the two tableaux and setting an offset turns them into one tableau that represents [PITH_FULL_IMAGE:figures/full_fig_p015_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Extending the tableau modeling v to make a valid tableau modeling u, a child of v. This generates upwards pointers for every external vertex of rhs(A), but since A → rhs(A) is the root of dt(A) these pointers just loop back to their origin. Note that this tableau models the path consisting only of the root of dt(A) by Definition 4.1. Starting from this, the tableau tabk(A, x, σ) is constructed row by row,… view at source ↗
Figure 13
Figure 13. Figure 13: Grammar generating a Star such that there are exponentially many different contexts in the derivation tree. [PITH_FULL_IMAGE:figures/full_fig_p022_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Derivation tree for the grammar in Figure 13 with [PITH_FULL_IMAGE:figures/full_fig_p023_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Alternative grammar equivalent to the grammar in Figure 13 but with polynomially many distinct tableaux. [PITH_FULL_IMAGE:figures/full_fig_p023_15.png] view at source ↗
read the original 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 ($\sigma \in \Sigma$). Precomputing the data structure needs $O(|G||\Sigma|\kappa r h)$ space and $O(|G||\Sigma|\kappa rh^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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper presents a pointer-based data structure for constant-time traversal of the edges of an edge-labeled directed hypergraph given as a hyperedge-replacement grammar G of fixed rank κ, under the assumption that each vertex is incident to at most one σ-edge per direction (σ ∈ Σ). Preprocessing requires O(|G||Σ|κ r h) space and O(|G||Σ|κ r h²) time, where h is the derivation height and r the maximum terminal rank.

Significance. If correct, the result would provide a non-trivial constant-delay query mechanism on grammar-compressed hypergraphs without explicit decompression, under standard bounded-rank and bounded-degree restrictions. The explicit dependence on grammar size, alphabet, rank, and derivation height is a clear strength of the stated bounds.

major comments (1)
  1. The manuscript text provided consists solely of the abstract, which asserts the existence of the data structure together with the stated space and time bounds but supplies no construction, proof, or verification steps. Without these, the central claim cannot be assessed for correctness.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their comments on our paper. The primary concern appears to arise from an incomplete excerpt being reviewed, as the full manuscript contains the requested construction, algorithm, and proofs.

read point-by-point responses

  1. Referee: The manuscript text provided consists solely of the abstract, which asserts the existence of the data structure together with the stated space and time bounds but supplies no construction, proof, or verification steps. Without these, the central claim cannot be assessed for correctness.

    Authors: The full manuscript (beyond the abstract) presents the pointer-based data structure in detail, including the preprocessing procedure that builds the necessary pointers under the bounded-rank and per-vertex uniqueness assumptions, the traversal algorithm that achieves constant delay, and the proofs of correctness together with the space and time bounds O(|G||Σ|κ r h) and O(|G||Σ|κ r h²). These sections directly support the claims summarized in the abstract. If the referee received only the abstract, we are happy to provide the complete text or specific sections for verification. revision: no

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents an explicit algorithmic construction of a pointer-based data structure for constant-time edge traversal on hyperedge-replacement grammars of fixed rank under a stated degree restriction. The abstract and claim give concrete preprocessing bounds O(|G||Σ|κ r h) space and O(|G||Σ|κ r h²) time directly in terms of the input grammar size, alphabet, rank, and derivation height; these are not obtained by fitting parameters to a subset of the target output or by renaming a known result. No self-citation is invoked as a load-bearing uniqueness theorem, no ansatz is smuggled, and no equation reduces the claimed traversal time to a definition of the same quantity. The result is therefore a self-contained construction whose correctness can be verified against the stated assumptions without circular reduction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on two explicit domain assumptions about the input grammar and graph; no free parameters or new entities are introduced in the abstract.

axioms (2)
  • domain assumption The grammar has a fixed rank κ
    Stated explicitly as an assumption in the abstract.
  • domain assumption Each vertex of the represented graph is incident to at most one σ-edge per direction (σ ∈ Σ)
    Stated explicitly as an assumption in the abstract.

pith-pipeline@v0.9.0 · 5678 in / 1240 out tokens · 30182 ms · 2026-05-24T16:39:25.109864+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · 1 internal anchor

  1. [1]

    Arroyuelo, R

    D. Arroyuelo, R. C´ anovas, G. Navarro, K. Sadakane, Succinct Trees in Practice, in: ALENEX, 84–97, 2010. 23

    work page 2010

  2. [2]

    Bannai, Grammar Compression, in: Encyclopedia of Algorithms, Springer-Verlag, New York, 861–866, 2016

    H. Bannai, Grammar Compression, in: Encyclopedia of Algorithms, Springer-Verlag, New York, 861–866, 2016

    work page 2016

  3. [3]

    M. A. Bender, M. Farach-Colton, The Level Ancestor Problem simplified, Theor. Comput. Sci. 321 (1) (2004) 5–12, URL https://doi.org/10.1016/j.tcs.2003.05.002

    work page doi:10.1016/j.tcs.2003.05.002 2004

  4. [4]

    Bille, I

    P. Bille, I. L. Gørtz, G. M. Landau, O. Weimann, Tree compression with top trees, Inf. Comput. 243 (2015) 166–177, URL https://doi.org/10.1016/j.ic.2014.12.012

    work page doi:10.1016/j.ic.2014.12.012 2015

  5. [5]

    Bille, G

    P. Bille, G. M. Landau, R. Raman, K. Sadakane, S. R. Satti, O. Weimann, Random Access to Grammar-Compressed Strings and Trees, SIAM J. Comp. 44 (3) (2015) 513–539

    work page 2015

  6. [6]

    Busatto, M

    G. Busatto, M. Lohrey, S. Maneth, Efficient memory representation of XML document trees, Inf. Syst. 33 (4-5) (2008) 456–474

    work page 2008

  7. [7]

    Claude, Personal Communication, 2010

    F. Claude, Personal Communication, 2010

    work page 2010

  8. [8]

    Drewes, H

    F. Drewes, H. Kreowski, A. Habel, Hyperedge Replacement Graph Grammars, in: Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations, World Scientific Publishing Co Pte Ltd, 95–162, 1997

    work page 1997

  9. [9]

    Engelfriet, Context-free graph grammars, in: Handbook of Formal Languages, Volume 3: Beyond words, Springer- Verlag, Berlin, Heidelberg, 125–213, 1997

    J. Engelfriet, Context-free graph grammars, in: Handbook of Formal Languages, Volume 3: Beyond words, Springer- Verlag, Berlin, Heidelberg, 125–213, 1997

    work page 1997

  10. [10]

    Ganardi, A

    M. Ganardi, A. Jez, M. Lohrey, Balancing Straight-Line Programs, CoRR abs/1902.03568, URL http://arxiv.org/abs/ 1902.03568

    work page arXiv 1902

  11. [11]

    Gasieniec, R

    L. Gasieniec, R. M. Kolpakov, I. Potapov, P. Sant, Real-Time Traversal in Grammar-Based Compressed Files, in: DCC, 458, 2005

    work page 2005

  12. [12]

    Gusfield, Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology, Cambridge University Press, 1997

    D. Gusfield, Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology, Cambridge University Press, 1997

    work page 1997

  13. [13]

    Habel, Hyperedge Replacement: Grammars and Languages, Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg, 1992

    A. Habel, Hyperedge Replacement: Grammars and Languages, Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg, 1992

    work page 1992

  14. [14]

    A. Jez, M. Lohrey, Approximation of smallest linear tree grammar, Inf. Comput. 251 (2016) 215–251, URL https: //doi.org/10.1016/j.ic.2016.09.007

    work page doi:10.1016/j.ic.2016.09.007 2016

  15. [15]

    Lohrey, Algorithmics on SLP-compressed strings: A survey, Groups Complexity Cryptology 4 (2012) 241–299

    M. Lohrey, Algorithmics on SLP-compressed strings: A survey, Groups Complexity Cryptology 4 (2012) 241–299

    work page 2012

  16. [16]

    Lohrey, Grammar-Based Tree Compression, in: DLT, 46–57, 2015

    M. Lohrey, Grammar-Based Tree Compression, in: DLT, 46–57, 2015

    work page 2015

  17. [17]

    Lohrey, S

    M. Lohrey, S. Maneth, R. Mennicke, XML tree structure compression using RePair, Inf. Syst. 38 (8) (2013) 1150–1167

    work page 2013

  18. [18]

    Lohrey, S

    M. Lohrey, S. Maneth, C. P. Reh, Constant-Time Tree Traversal and Subtree Equality Check for Grammar-Compressed Trees, Algorithmica 80 (7) (2018) 2082–2105

    work page 2018

  19. [19]

    Lohrey, S

    M. Lohrey, S. Maneth, M. Schmidt-Schauß, Parameter reduction and automata evaluation for grammar-compressed trees, J. Comput. Syst. Sci. 78 (5) (2012) 1651–1669

    work page 2012

  20. [20]

    Maneth, Grammar-Based Compression, in: Encyclopedia of Big Data Technologies., URL https://doi.org/10.1007/ 978-3-319-63962-8_56-1 , 2019

    S. Maneth, Grammar-Based Compression, in: Encyclopedia of Big Data Technologies., URL https://doi.org/10.1007/ 978-3-319-63962-8_56-1 , 2019

    work page 2019

  21. [21]

    Maneth, F

    S. Maneth, F. Peternek, Constant Delay Traversal of Compressed Graphs, in: DCC, 32–41, 2018

    work page 2018

  22. [22]

    Maneth, F

    S. Maneth, F. Peternek, Grammar-based graph compression, Inf. Syst. 76 (2018) 19–45

    work page 2018

  23. [23]

    Fast and Tiny Structural Self-Indexes for XML

    S. Maneth, T. Sebastian, Fast and Tiny Structural Self-Indexes for XML, CoRR abs/1012.5696

    work page internal anchor Pith review Pith/arXiv arXiv

  24. [24]

    Navarro, K

    G. Navarro, K. Sadakane, Fully Functional Static and Dynamic Succinct Trees, ACM Trans. Algorithms 10 (3) (2014) 16:1–16:39

    work page 2014

  25. [25]

    Schieber, U

    B. Schieber, U. Vishkin, On Finding Lowest Common Ancestors: Simplification and Parallelization, SIAM J. Comput. 17 (6) (1988) 1253–1262. 24

    work page 1988