Traversing Grammar-Compressed Trees with
Constant Delay

arXiv:1511.02141v2 [] 10 Nov 2015

Markus Lohrey1 , Sebastian Maneth2 , and Carl Philipp Reh1
1
2

Universität Siegen, Germany
University of Edinburgh, UK

Abstract
A grammar-compressed ranked tree is represented with a linear space
overhead so that a single traversal step, i.e., the move to the parent or the
ith child, can be carried out in constant time. Moreover, we extend our data
structure such that equality of subtrees can be checked in constant time.

1 Introduction
Context-free grammars that produce single strings are a widely studied compact
string representation and are also known as straight-line programs (SLPs). For
instance, the string (ab)1024 can be represented by the SLP with the rules A0 → ab
and Ai → Ai−1 Ai−1 for 1 ≤ i ≤ 10 (A10 is the start symbol). In general, an SLP
of size n can produce a string of length 2Ω(n) . Besides grammar-based compressors
(e.g. LZ78, RePair, or BISECTION, see [7] for more details) that derive an SLP
from a given string, also algorithmic problems on SLP-compressed strings such as
pattern matching, indexing, and compressed word problems have been investigated
thoroughly, see [16] for a survey.
Motivated by applications where large tree structures occur, like XML processing, SLPs have been extended to node-labelled ranked ordered trees [4, 5, 12,
15, 18]. In those papers, straight-line linear context-free tree grammars are used.
Such grammars produce a single tree and are also known as tree straight-line programs (TSLPs). TSLPs generalize dags (directed acyclic graphs), which are widely
used as compact tree representation. Whereas dags only allow to share repeated
subtrees, TSLPs can also share repeated internal tree patterns (i.e., connected subgraphs). The grammar-based tree compressor from [12] produces for every tree
(for a fixed set of node labels) a TSLP of size O( logn n ) and height O(log n), which
is worst-case optimal. Various querying problems on TSLP-compressed trees such
as XPath querying and evaluating tree automata are studied in [17, 19, 21].
In this paper we study the problem of navigating in a TSLP-represented tree:
Given a TSLP G for a tree t, the task is to precompute in time O(|G|) an O(|G|)space data structure that allows to move from a node of t in time O(1) to its parent
1

node or to its ith child and to return in time O(1) the node label of the current node.
Here the nodes of t are represented in space O(|G|) in a suitable way. Such a data
structure has been developed for string SLPs in [10]; it allows to move from left
to right over the string produced by the SLP requiring time O(1) per move. We
first extend the data structure from [10] so that the string can be traversed in a twoway fashion, i.e., in each step we can move either to the left or right neighboring
position in constant time. This data structure is then used to navigate in a TSLPrepresented tree.
TSLPs are usually used for the compression of ranked trees, i.e., trees where the
maximal number r of children of a node is bounded by a constant. For instance,
the above mentioned bound O( logn n ) from [12] assumes a constant r. In many
applications, r is indeed bounded (e.g., r = 2 for the following two encodings of
unranked trees). For unranked trees where r is unbounded, it is more realistic to
require that the data structure supports navigation to (i) the parent node, (ii) the
first child, (iii) the right sibling, and (iv) the left sibling. We can realize these
operations by using a suitable constant-rank encoding of trees. Two folklore binary
tree encodings of an unranked tree t with maximal rank r are:
• First-child/next-sibling encoding fcns(t): The left (resp. right) child of a
node in fcns(t) is the first child (resp., right sibling) in t. On this encoding,
we can support O(1) time navigation for (ii)–(iv) of above. The parent move
(i) however, requires O(r) time.
• Binary encoding: We define the binary encoding bin(t) by adding for every
node v of rank s ≤ r a binary tree of depth ⌈log s⌉ with s many leaves, whose
root is v and whose leaves are the children of v. This introduces at most 2s
many new binary nodes (labelled by a new symbol). Thus |bin(t)| ≤ 3|t|.
Every navigation step in the original tree can be simulated by O(log r) many
navigation steps in bin(t).
Our second main result concerns subtree equality checks. This is the problem of
checking for two given nodes of a tree, whether the subtrees rooted at these two
node are identical. We extend our data structure for tree navigation such that subtree equality checks can be done in time O(1). The problem of checking equality
of subtrees occurs in several different contexts, see for instance [6] for details.
Typical applications are common subexpression detection, unification, and nonlinear pattern matching. For instance, checking whether the pattern f (x, f (y, y))
is matched at a certain tree node needs a constant number of navigation steps and
a single subtree equality check.
Further related work. The ability to navigate efficiently in a tree is a basic prerequisite for most tree querying procedures. For instance, the DOM representation
available in web browsers through JavaScript, provides tree navigation primitives
(see, e.g., [9]). Tree navigation has been intensively studied in the context of succinct tree representations. Here, the goal is to represent a tree by a bit string,
whose length is asymptotically equal to the information theoretic lower bound.
2

For instance, for binary trees of n nodes, the information theoretic lower bound
is 2n + o(n) and there exist succinct representations that encode a binary tree of
size n by a bit string of length 2n + o(n). In addition there exist such encodings
that allow to navigate in the tree in constant time (and support many other tree
operations), see e.g. [22] for a survey.
Recently, grammatical formalisms for the compression of unranked trees have
been proposed as well. In [2] the authors consider so called top dags as a compact tree representation. Top dag can be seen as a slight variant of TSLPs for an
unranked tree. It is shown in [2] that for every tree of size n the
top dag has size
n·log log n 
n
).
Recently,
this
bound
was
improved
to
O
in
[11] (it is open
O( log0.19
log n
n

whether this bound can be improved to the information theoretic limit O logn n ).
Moreover, also the navigation problem for top dags is studied in [2]. The authors
show that a single navigation step in t can be done in time O(log |t|) in the top
dag. Nodes are represented by their preorder numbers, which need O(log |t|) bits.
In [3] an analogous result has been shown for unranked trees that are represented
by a string SLP for the balanced bracket representation of the tree. This covers
also TSLPs: From a TSLP G one can easily compute in linear time an SLP for the
balanced bracket representation of val(G). In some sense our results are orthogonal
to the results of [3].
• We can navigate, determine node labels, and check equality of subtrees in
time O(1), but our representation of tree nodes needs space O(|G|).
• Bille et al. [3] can navigate and do several other tree queries (e.g. lowest
common ancestor computations) in time O(log |t|), but their node representations (preorder numbers) only need space O(log |t|) ≤ O(|G|).
An implementation of navigation over TSLP-compressed trees is given in [20].
Their worst-case time per navigation step is O(h) where h is the height of the
TSLP. The authors demonstrate that on XML data full traversals are 5–7 times
slower than over succinct trees (based on an implementation by Sadakane) while
using 3–15 times less space.
Checking equality of subtrees is trivial for minimal dags, since every subtree
is uniquely represented. For so called SL grammar-compressed dags (which can
be seen as TSLPs with certain restrictions) it was shown in [4] that equality of
subtrees can be checked in time O(log |t|) for given preorder numbers.

2 Preliminaries
For an alphabet Σ we denote by Σ∗ the set of all strings over Σ including the
empty string ǫ. For a string w = a1 · · · an (ai ∈ Σ) we denote by alph(w) the
set of symbols {a1 , . . . , an } occurring in w. Moreover, let |w| = n, w[i] = ai
and w[i : j] = ai · · · aj where w[i : j] = ε, if i > j. Let w[: i] = w[1 : i] and
w[i :] = w[i : n].
3

3 Straight-Line Programs
A straight-line program (SLP), is a triple H = (N, Σ, rhs), where N is a finite set
of nonterminals, Σ is a finite set of terminals (Σ∩N = ∅), and rhs : N → (N ∪Σ)∗
is a mapping such that the binary relation {(A, B) ∈ N × N | B ∈ alph(rhs(A))}
is acyclic. This condition ensures that every nonterminal X ∈ N produces a unique
string valH (X) ∈ Σ∗ . It is obtained from the string X by repeatedly replacing
nonterminals A by rhs(A), until no nonterminal occurs in the string. We will also
write A → α if rhs(A) = α and call it a rule of H. Usually, an SLP has a start
nonterminal as well, but for our purpose, it is more convenient to consider SLPs
without a start nonterminal.
P
The size of the SLP H is |H| =
A∈N |rhs(A)|, i.e., the total length of all
right-hand sides. A simple induction shows that for every SLP H of size m and
every nonterminal A, |valH (A)| ∈ O(3m/3 ) [7, proof of Lemma 1]. On the other
hand, it is straightforward to define an SLP H of size 2n such that |val(H)| ≥ 2n .
Hence, an SLP can be seen as a compressed representation of the string it generates,
and it can achieve exponential compression rates.
In Section 8 we will use some algorithmic facts about SLPs, which are collected in the following proposition, see [16] for details:
Proposition 1 There are polynomial time algorithms for the following problems:
• Given an SLP H and a position i, compute the symbol val(H)[i].
• Given an SLP H and two positions i < j, compute an SLP for the string
val(H)[i : j].
• Given two SLPs H1 and H2 , compute the length of the longest common
prefix of val(H1 ) and val(H2 ).

4 Tree Straight-Line Programs
For every i ≥ 0, we fix a countable infinite set Fi of terminals
S of rank i and a
countable
infinite
set
N
of
nonterminals
of
rank
i.
Let
F
=
i
i≥0 Fi and N =
S
N
.
Moreover,
let
X
=
{x
,
x
,
.
.
.
}
be
the
set
of
parameters.
We assume
1 2
i≥0 i
that the three sets F, N , and X are pairwise disjoint. A labeled tree t = (V, E, λ) is
a finite, directed and ordered tree t with set of nodes V , set of edges E ⊆ V ×N×V ,
and labeling function λ : V → F ∪ N ∪ X . We require for every node v ∈ V that
if λ(v) ∈ Fk ∪ Nk , then v has k distinct children u1 , . . . , uk , i.e., (v, i, u) ∈ E if
and only if 1 ≤ i ≤ k and u = ui . A leaf of t is a node with zero children. We
require that every node v with λ(v) ∈ X is a leaf of t. The size of t is |t| = |V |.
We denote trees in their usual term notation, e.g. a(b, c) denotes the tree with an
a-labeled root node that has a first child labeled b and a second child labeled c.
We define T as the set of all labeled trees. Let labels(t) = {λ(v) | v ∈ V }. For
L ⊆ F ∪ N ∪ X we let T (L) = {t ∈ T | labels(t) ⊆ L}. The tree t ∈ T is
4

linear if there do not exist different leaves that are labeled with the same parameter.
We now define a particular form of context-free tree grammars (see [8] for more
details on context-free tree grammars) with the property that exactly one tree is
derived. A tree straight-line program (TSLP) is a triple G = (N, S, rhs), where
N ⊆ N is a finite set of nonterminals, S ∈ N0 ∩ N is the start nonterminal, and
rhs : N → T (F ∪ N ∪ X ) is a mapping such that the following hold:
• For every A ∈ N , the tree rhs(A) is linear and if A ∈ Nk (k ≥ 0) then
X ∩ labels(rhs(A)) = {x1 , . . . , xk }.
• The binary relation {(A, B) ∈ N × N | B ∈ labels(rhs(A))} is acyclic.
These conditions ensure that from every nonterminal A ∈ N ∩ Nk exactly one
linear tree valG (A) ∈ T (F ∪ {x1 , . . . , xk }) is derived by using the rules A →
rhs(A) as rewrite rules in the usual sense. More generally, for every tree t ∈ T (F ∪
N ∪ {x1 , . . . , xn }) we can derive a unique tree valG (t) ∈ T (F ∪ {x1 , . . . , xn })
with the rules of G. The tree defined by G is val(G) = valG (S). Instead of giving a
formal definition, we show a derivation of val(G) from S in an example:
Example 1 Let G = ({S, A, B, C, D, E, F }, S, rhs), a ∈ F0 , and b ∈ F2 , where
rhs(S) = A(B), rhs(A) = C(F, x1 ), rhs(B) = E(F ), rhs(C) = D(E(x1 ), x2 ),
rhs(D) = b(x1 , x2 ), rhs(E) = D(F, x1 ), rhs(F ) = a.
A possible derivation of val(G) = b(b(a, a), b(a, a)) from S is:
S → A(B) → C(F, B) → D(E(F ), B) → b(E(F ), B) → b(D(F, F ), B)
→ b(b(F, F ), B) → b(b(a, F ), B) → b(b(a, a), B) → b(b(a, a), E(F ))
→ b(b(a, a), D(F, F )) → b(b(a, a), b(F, F )) → b(b(a, a), b(a, F ))
→ b(b(a, a), b(a, a)).
As for SLPs, we will also write A →
Pt if rhs(A) = t. The size |G| of a TSLP
G = (N, S, rhs) is defined as |G| = A∈N |rhs(A)| (recall that we do not count
parameters). For instance, the TSLP from Example 1 has size 12.
A TSLP G = (N, rhs, S) is monadic if N ⊆ N0 ∪ N1 , i.e., every nonterminal
has rank at most 1. The following result is shown in [19].
Proposition 2 From a given TSLP G, where r and k are the maximal ranks of
terminal and nonterminal symbols appearing in a right-hand side, one can construct
in time O(r · k · |G|) a monadic TSLP H such that val(H) = val(G) and |H| ∈
O(r · |G|).
Finally, we need the following algorithmic result from [5]:
Proposition 3 For two TSLPs G1 and G2 we can check in polynomial time whether
val(G1 ) = val(G2 ).
5

5 Computational model
We use the word RAM model in the following sections, where registers have a
certain bit length w. Arithmetic operations and comparisons of registers can be
done in time O(1). The space of a data structure is measured by the number of
registers. Our algorithms need the following register lengths w, where G is the
input TSLP and t = val(G).
• For navigation (Section 7) we need a bit length of w = O(log |G|), since we
only have to store numbers of length at most |G|.
• For equality checks (Section 8) we need a bit length of w = O(log |t|) ≤
O(|G|), which is the same assumption as in [2, 3].

6 Two-Way Traversal in SLP-Compressed Strings
In [10] the authors present a data structure of size O(|H|) for storing an SLP H
that allows to produce valH (A) with time delay of O(1) per symbol. That is, the
symbols of valH (A) are produced from left to right and for each symbol constant
time is needed.
In a first step, we enhance the data structure from [10] for traversing SLPcompressed strings in such a way that both operations of moving to the left and
right symbol are supported in constant time. For this, we assume that the SLP
H = (N, Σ, rhs) has the property that |rhs(A)| = 2 for each A ∈ N . Every SLP H
with |val(H)| ≥ 2 can easily be transformed in linear time into an SLP H′ with this
property and val(H′ ) = val(H): First, we replace all occurrences of nonterminals
B with |rhs(B)| ≤ 2 by rhs(B). If rhs(S) = A ∈ N , then we redefine rhs(S) =
rhs(A). Finally, for every A ∈ N such that rhs(A) = α1 · · · αn with n ≥ 3
and α1 , . . . , αn ∈ (N ∪ Σ) we introduce new nonterminals A2 , . . . , An−1 with
rules Ai → αi Ai+1 for 2 ≤ i ≤ n − 2, and An−1 → αn−1 αn , and redefine
rhs(A) = α1 A2 . It should be clear that |H′ | ≤ 2 · |H|.
Note that the positions in valH (X) correspond to root-leaf paths in the (binary)
derivation tree of H that is rooted in the nonterminal X. We represent such a path
by merging successive edges where the path moves in the same direction (left or
right) towards the leaf. To formalize this idea, we define for every α ∈ N ∪ Σ the
strings L(α), R(α) ∈ N ∗ Σ inductively as follows: For a ∈ Σ let
L(a) = R(a) = a.
For A ∈ N with rhs(A) = αβ (α, β ∈ N ∪ Σ) let
L(A) = A L(α) and R(A) = A R(β).

(1)

Note that for every A ∈ N , the string L(A) has the form A1 A2 · · · An a with
Ai ∈ N , A1 = A, and a ∈ Σ. We define ωL (A) = a. The terminal ωR (A) is
defined analogously by referring to the string R(A).
6

a
C

a

b

b
D

D

B

C

A

A

S

D
S

Figure 1: The tries TL (a), TL (b) (left), and TR (a), TR (b) (right) for the SLP from
Example 2.

Example 2 Let H = ({S, A, B, C, D}, {a, b}, rhs), where
S → AB, A → BC, B → CC, C → aD, D → ab.
Then we have L(S) = SABCa, L(A) = ABCa, L(B) = BCa, L(C) = Ca,
L(D) = Da, R(S) = SBCDb, R(A) = ACDb, R(B) = BCDb, R(C) =
CDb, R(D) = Db. Moreover, ωL (X) = a and ωR (X) = b for all X ∈
{S, A, B, C, D}.
We store all strings L(A) (for A ∈ N ) in |Σ| many tries: Fix a ∈ Σ and let
w1 , . . . , wn be all strings L(A) such that ωL (A) = a. Let vi be the string wi
reversed. Then, a, v1 , . . . , vn is a prefix-closed set of strings (except that the empty
string is missing) that can be stored in a trie TL (a). Formally, the nodes of TL (a)
are the strings a, v1 , . . . , vn , where each node is labeled by its last symbol (so the
root is labeled with a), and there is an edge from aw to awA for all appropriate
w ∈ N ∗ and A ∈ N . The tries TR (a) are defined in the same way by referring to
the strings R(A). Note that the total number of nodes in all tries TL (a) (a ∈ Σ) is
exactly |N | + |Σ|. In fact, every α ∈ N ∪ Σ occurs exactly once as a node label in
the forest {TL (a) | a ∈ Σ}.
Example 3 (Example 2 continued) The tries TL (a), TL (b), TR (a), and TR (b) for
the SLP from Example 2 are shown in Figure 1.
Next, we define two alphabets L and R as follows:
L ={(A, ℓ, α) | α ∈ alph(L(A)) \ {A}}

(2)

R ={(A, r, β) | β ∈ alph(R(A)) \ {A}}

(3)

Note that the sizes of these alphabets are quadratic in the size of H. On the alphabets L and R we define the partial operations reduceL : L → L and reduceR :
7

R → R as follows: Let (A, ℓ, α) ∈ L. Hence we can write L(A) as Auαv for some
strings u and v. If u = ε, then reduceL (A, ℓ, α) is undefined. Otherwise, we can
write u as u′ B for some B ∈ N . Then we define reduceL (A, ℓ, α) = (A, ℓ, B).
The definition of reduceR is analogous: If (A, r, α) ∈ R, then we can write R(A)
as Auαv for some strings u and v. If u = ε, then reduceR (A, r, α) is undefined.
Otherwise, we can write u as u′ B for some B ∈ N and define reduceR (A, r, α) =
(A, r, B).
Example 4 (Example 2 continued) The sets L and R are:
L = {(S, ℓ, A), (S, ℓ, B), (S, ℓ, C), (S, ℓ, a), (A, ℓ, B),
(A, ℓ, C), (A, ℓ, a), (B, ℓ, C), (B, ℓ, a), (C, ℓ, a), (D, ℓ, a)}
R = {(S, r, B), (S, r, C), (S, r, D), (S, r, b), (A, r, C), (A, r, D),
(A, r, b), (B, r, C), (B, r, D), (B, r, b), (C, r, D), (C, r, b), (D, r, b)}.
For instance, reduceL (S, ℓ, a) = (S, ℓ, C) and reduceR (B, r, D) = (B, r, C)
whereas reduceL (S, ℓ, A) is undefined.
An element (A, ℓ, α) can be represented by a pair (v1 , v2 ) of different nodes in the
forest {TL (a) | a ∈ Σ}, where v1 (resp. v2 ) is the unique node labeled with α
(resp., A). Note that v1 and v2 belong to the same trie and that v2 is below v1 .
This observation allows us to reduce the computation of the mapping reduceL to
a so-called next link query: From the pair (v1 , v2 ) we have to compute the unique
child v of v1 such that v is on the path from v1 to v2 . If v is labeled with B, then
reduceL (A, ℓ, α) = (A, ℓ, B), which is represented by the pair (v, v2 ). Clearly,
the same remark applies to the map reduceR . The following result is mentioned
in [10], see Section 9 for a discussion.
Proposition 4 A trie T can be represented in space O(|T |) such that any next
link query can be answered in time O(1). Moreover, this representation can be
computed in time O(|T |) from T .
We represent a path in the derivation tree of H with root X by a sequence of triples
γ = (A1 , d1 , A2 )(A2 , d2 , A3 ) · · · (An−1 , dn−1 , An )(An , dn , a) ∈ (L ∪ R)+
such that n ≥ 1 and the following properties hold:
• A1 = X, a ∈ Σ
• di = ℓ if and only if di+1 = r for all 1 ≤ i ≤ n − 1.
We call such a sequence a valid X-sequence for H in the following, or briefly a
valid sequence if X is not important and H is clear from the context. Note that
a valid X-sequence γ indeed defines a unique path in the derivation tree rooted
at X that ends in a leaf that is labelled with the terminal symbol a if γ ends with
8

Algorithm 1: right(γ)
Data: valid sequence γ
(A, d, a) := pop(γ) ;
if d = ℓ then
expand-right(γ, A, a)
else
if γ = ε then
return undefined
else
(A′ , ℓ, A) := pop(γ) ;
γ := expand-right(γ, A′ , A)
end
end
return γ

(A, d, a). This path, in turn, defines a unique position in the string valH (X) that
we denote by pos(γ).
We now define a procedure right (see Algorithm 1) that takes as input a valid
X-sequence γ and returns a valid X-sequence γ ′ such that pos(γ ′ ) = pos(γ) + 1
in case the latter is defined (and otherwise returns “undefined”). The idea uses the
obvious fact that in order to move in a binary tree from a leaf to the next leaf (where
“next” refers to the natural left-to-right order on the leaves) one has to repeatedly
move to parent nodes as long as right-child edges are traversed (in the opposite
direction); when this is no longer possible, the current node is the left child of its
parent p. One now moves to the right child of p and from here repeatedly to leftchildren until a leaf is reached. Each of these four operations can be implemented
in constant time on valid sequences, using the fact that consecutive edges to left
(resp., right) children are merged into a single triple from L (resp., R) in our representation of paths. We use the valid sequence γ as a stack with the operations
pop (which returns the right-most triple of γ, which is thereby removed from γ)
and push (which appends a given triple on the right end of γ). The procedure right
uses the procedure expand-right (see Algorithm 2) that takes as input a (non-valid)
sequence γ of triples, A ∈ N , and a symbol α ∈ N ∪ Σ such that γ(A, ℓ, α) is a
prefix of a valid sequence. The sequence γ has to be treated as a global variable in
order to obtain an O(1)-time implementation (to make the presentation clearer, we
pass γ as a parameter to expand-right).
In a completely analogous way we can define a procedure left that takes as
input a valid X-sequence γ and returns a valid X-sequence γ ′ such that pos(γ ′ ) =
pos(γ) − 1 in case the latter is defined (otherwise “undefined” will be returned).
The details are left to the reader.

9

Algorithm 2: expand-right(γ, A, α)
Data: sequence γ, A ∈ N , α ∈ N ∪ Σ such that γ(A, ℓ, α) is a prefix of a
valid sequence
let rhs(A) = α1 α2 ;
if α 6= α1 then
(A, ℓ, B) := reduceL (A, ℓ, α) ;
push(γ, (A, ℓ, B)) ;
let rhs(B) = β1 β2 ;
push(γ, (B, r, β2 ));
if β2 ∈ N then
push(γ, (β2 , ℓ, ωL (β2 )))
end
else
if γ = ε then
push(γ, (A, r, α2 ))
else
(B, r, A) := pop(γ) ;
push(γ, (B, r, α2 ))
end
if α2 ∈ N then
push(γ, (α2 , ℓ, ωL (α2 )))
end
end
return γ

7 Traversal in TSLP-Compressed Trees
In this section, we extend the traversal algorithm from the previous section from
SLPs to TSLPs. We only consider monadic TSLPs. If the TSLP is not monadic,
then we can transform it into a monadic TSLP using Proposition 2.
Let us fix a monadic TSLP G = (N, rhs, S). One can easily modify G so that
for all A ∈ N , rhs(A) has one of the following four forms (we write x for the
parameter x1 ):
(a) B(C) for B, C ∈ N (and A has rank 0)
(b) B(C(x)) for B, C ∈ N (and A has rank 1)
(c) a ∈ F0 (and A has rank 0)
(d) f (A1 , . . . , Ai−1 , x, Ai+1 , . . . , An ) for A1 , . . . , Ai−1 , Ai+1 , . . . , An ∈ N , f ∈
Fn , n ≥ 1 (and A has rank 1)
This modification is done in a similar way as the transformation of SLPs at the
beginning of Section 6: Remove nonterminals A ∈ N1 with rhs(A) = x1 (resp.,
10

rhs(A) = B(x1 ), B ∈ N ) by replacing in all right-hand sides every subtree A(t)
by t (resp., B(t)) and iterate this as long as possible. Similarly, we can eliminate
nonterminals A ∈ N0 \ {S} with rhs(A) ∈ N . If rhs(S) = B ∈ N0 then redefine
rhs(S) := rhs(B). Finally, right-hand sides of size at least two are split top-down
into new nonterminals with right-hand sides of the above types. In case the righthand side contains the parameter x1 (in a unique position), we decompose along
the path to x1 . For example, the rule Z(x) → h(f (A, a), f (A, g(x)), B(A)) is
replaced by Z(x) → C(D(x)), C(x) → h(E, x, F ), D(x) → G(H(x)), E →
G(J), F → B(A), G(x) → f (A, x), H(x) → g(x), J → a. The resulting TSLP
has size at most 2|G|.
Let us write Nx (x ∈ {a, b, c, d}) for the set of all nonterminals whose righthand side is of the above type (x). Let N1 = Na ∪ Nb and N2 = Nc ∪ Nd .
Note that if we start with a nonterminal A ∈ Na and then replace nonterminals
from N1 by their right-hand sides repeatedly, we obtain a tree that consists of
nonterminals from Nd followed by a single nonterminal from Nc . After replacing
these nonterminals by their right-hand sides, we obtain a caterpillar tree which is
composed of right-hand sides of the form (d) followed by a single constant from
F0 . Hence, there is a unique path of terminal symbols from F, and we call this path
the spine path of A. All other nodes of the caterpillar tree are leaves and labeled
with nonterminals of rank zero to which we can apply again the TSLP rules. The
size of a caterpillar tree and therefore a spine path can be exponential in the size of
the TSLP.
We define an SLP H = (N1 , N2 , rhs1 ) as follows: If A ∈ N1 with rhs(A) =
B(C) or rhs(A) = B(C(x)), then rhs1 (A) = BC. The triple alphabets L and
R from (2) and (3) refer to this SLP H. Moreover, we define M to be the set of
all triples (A, k, Ak ) where A ∈ Nd , rhs(A) = f (A1 , . . . , Ai−1 , x, Ai+1 , . . . , An )
and k ∈ {1, . . . , n} \ {i}.
Note that the nodes of the tree val(G) can be identified with the nodes of G’s
derivation tree that are labeled with a nonterminal from N2 (every nonterminal
from N2 has a unique occurrence of a terminal symbol on its right-hand side).
A valid sequence for G is a sequence
γ = (A1 , e1 , A2 )(A2 , e2 , A3 ) · · · (An−1 , en−1 , An )(An , en , An+1 ) ∈ (L∪R∪M )∗
(note that e1 , . . . , en ∈ {ℓ, r} ⊎ N) such that n ≥ 0 and the following hold:
• If S ∈ Na then n ≥ 1.
• If n ≥ 1 then A1 = S and An+1 ∈ N2 .
• If ei , ei+1 ∈ {ℓ, r} then ei = ℓ if and only if ei+1 = r.
Such a valid sequence represents a path in the derivation of the TSLP G from the
root to an N2 -labelled node, and hence represents a node of the tree val(G). Note
that in case S ∈ Nc the empty sequence is valid too and represents the unique node
of the single-node tree val(G). Moreover, if the last triple (An , en , An+1 ) belongs
to M , then we must have An+1 ∈ Nc , i.e., rhs(An+1 ) ∈ F0 . Here is an example:
11

Example 5 Consider the monadic TSLP G with nonterminals S, A, B, C, D, E,
F , G, H, J and the following rules
S → A(B), A → C(D(x)), B → C(E), C → f (F, x), D → f (x, F ),
E → D(F ), F → G(H), G → J(J(x)), H → a, J → g(x).
It produces the tree shown in Figure 2. We have N1 = {S, A, B, E, F, G} and
N2 = {C, D, J}. The SLP H consists of the rules
S → AB, A → CD, B → CE, E → DF, F → GH, G → JJ
(the terminal symbols are C, D, H, J). The triple set M is
M = {(C, 1, F ), (D, 2, F )}.
A valid sequence is for instance (S, ℓ, A)(A, r, D)(D, 2, F )(F, ℓ, J). It represents
the circled g-labelled node in Figure 2.
From a valid sequence γ we can clearly compute in time O(1) the label of the tree
node represented by γ. Let us denote this terminal symbol with label(γ): If γ ends
with the triple (A, e, B), then we have B ∈ N2 and label(γ) is the unique terminal
symbol in rhs(B). If γ = ε, then S ∈ Nc and label(γ) is the unique terminal
symbol in rhs(S).
Using valid sequences of G it is easy to do a single navigation step in constant
time. Let us fix a valid sequence γ. We consider the following possible navigation
steps: Move to the parent node (if it exists) and move to the ith child (if it exists).
Consider for instance the navigation to the ith child. First we check whether 1 ≤
i ≤ r, where r is the rank of label(γ). If this does not hold, then we return
undefined. Otherwise, γ does not represent a leaf of val(G) and therefore γ can
be neither empty nor end with a triple from M ∪ (N × {ℓ, r} × Nc ). Let β 6= ε
be the maximal suffix of γ, which belongs to (L ∪ R)∗ . Then β represents a path
in the derivation tree of the string SLP H that is rooted in a certain nonterminal
A ∈ Na and that leads to a certain nonterminal B ∈ Nd . This path corresponds
to a node of valG (A) that is located on the spine path of A. We can now apply our
SLP-navigation algorithms left and right to the sequence β in order to move up or
down on the spine path. More precisely, let β end with the triple (C, d, B) (we
must have d ∈ {ℓ, r} and B ∈ Nd ). We can now distinguish the following cases,
where f (A1 , . . . , Aj−1 , x, Aj+1 , . . . , An ) is the right-hand side of B:
(i) i 6= j: Then we obtain the ith child by appending to γ the triple (B, i, Ai ) ∈
M followed by the path that represents the root of Ai (which consists of at
most one triple).
(ii) i = j: Then we obtain the ith child of the current node by moving down on
the spine path. Thus, we replace the suffix β by right(β).

12

Algorithm 3: parent(γ)
Data: valid sequence γ
if γ ∈ {ε} ∪ L then
return undefined
end
if γ belongs to α · M · L or α · M for some α ∈ (L ∪ R ∪ M )∗ then
return α ; (Note that α must be a valid sequence.)
end
let γ = α · β, where α ∈ {ε} ∪ (L ∪ R ∪ M )∗ · M and β ∈ (L ∪ R)+ ;
return α· left(β) ;
(We have β 6∈ L, hence left(β) 6=
undefined.)
Algorithm 4: child(γ, i)
Data: valid sequence γ, number i
if i > r, where r is the rank of label(γ) then
return undefined
end
let γ = α · β, where α ∈ {ε} ∪ (L ∪ R ∪ M )∗ · M and β ∈ (L ∪ R)+ ;
let β end with the triple (C, d, B);
(We must have B ∈ Nd .)
let rhs(B) = f (A1 , . . . , Aj−1 , x1 , Aj+1 , . . . , An ) ;
if i = j then
return α · right(β)
end
return α · β · (B, i, Ai ) · root(Ai )
Similar argument can be used to navigate to the parent node.
Algorithm 3 shows the pseudo code for moving to the parent node, and Algorithm 4 shows the pseudo code for moving to the i-th child. If this node does not
exist, then “undefined” is returned. To make the code more readable we denote the
concatenation operator for sequences of triples (or sets of triple sequences) with
“·”. We make use of the procedures left and right from Section 6, applied to the
SLP H derived from our TSLP G. Note that in Algorithm 3 we apply in the final
case the procedure left to the maximal suffix β from (L ∪ R)+ of the current valid
sequence γ (and similarly for Algorithm 4). To provide an O(1) time implementation we do not copy the sequence β and pass it to left (which is not possible in
constant time) but apply left directly to γ. The right-most triple from M in γ (if it
exists) works as a left-end marker. Algorithm 4 uses the procedure root(A) (with
A of rank 0). This procedure is not shown explicitly: It simply returns ǫ if A ∈ N2 ,
and otherwise returns (A, ℓ, ωL (A)) (recall ωL from Page 6). Hence, it returns the
representation of the root node of valG (A).
The following theorem summarizes the results of this section:
Theorem 1 Given a monadic TSLP G we can compute in linear time on a word
13

f
g

f

g
a

g

f
g

g

f

g

g

g

a

g

g

a

a

a

Figure 2: The tree produced from the TSLP in Example 5

RAM with register length O(log |G|) a data structure of size O(|G|) that allows
to do the following computations in time O(1), where γ is a valid sequence that
represents the tree node v: (1) Compute the valid sequence for the parent node of
v, and (2) compute the valid sequence for the ith child of v.

8 Equality checks
Consider a monadic TSLP G = (N, rhs, S), where again for every nonterminal
A ∈ N , rhs(A) has one of the following four forms:
(a) B(C) for B, C ∈ N (and A has rank 0)
(b) B(C(x)) for B, C ∈ N (and A has rank 1)
(c) a ∈ F0 (and A has rank 0)
(d) f (A1 , . . . , Ai−1 , x, Ai+1 , . . . , An ) for A1 , . . . , Ai−1 , Ai+1 , . . . , An ∈ N , f ∈
Fn , n ≥ 1 (and A has rank 1)
Let t = val(G) be the tree produced by G. The goal of this section is to extend
the navigation algorithm from the previous section such that for two nodes of t
(represented by valid sequences) we can test in O(1) time whether the subtrees
rooted at the two nodes are equal. Recall from Section 5 that we use the word
RAM model with registers of length O(log |t|). This is the same assumption that
is also used in [2, 3]. As before, the preprocessed data structure will have size
O(|G|) and the query time will be O(1). But this time, the preprocessing time will
14

f
f
A

E
f

C

f
A

a

Figure 3: The caterpillar tree produced from S of the TSLP in Example 6

be polynomial in the TSLP size |G| and not just linear. It will be hard to reduce
this to linear time preprocessing. The best known algorithm for checking equality
of SLP-compressed strings has quadratic complexity [14], and from two SLPs H1
and H2 we can easily compute a TSLP for a tree t whose root has two children in
which val(H1 ) and val(H2 ) are rooted as linear chains.
We assume that G is reduced in the sense that valG (A) 6= valG (B) for all
A, B ∈ N with A 6= B. Reducing the TSLP does not increase its size and the
reduction can be done in polynomial time (recall that we allow polynomial time
preprocessing) by Proposition 3. To motivate the forthcoming definitions, we first
give an example of two equal subtrees produced by a single TSLP.
Example 6 Consider the TSLP G with the following rules:
S → G(A), A → a, B(x) → f (A, x), C → B(A), D(x) → f (C, x),
E → D(C), F (x) → f (x, E), G(x) → H(I(x)), H(x) → F (B(x)),
I(x) → D(B(x))
The reader can check that this TSLP is reduced. The caterpillar tree of S is given
in Figure 3. The tree produced by the subtree surrounded by a square is the same
as the one produced by E.
We use the notations introduced in the previous section. For a string
w = A1 A2 · · · An An+1 ∈ Nd∗ Nc
we define
valG (w) = valG (A1 (A2 (· · · An (An+1 ) · · · ))).
Recall the definition of the SLP H = (N1 , N2 , rhs1 ) from Section 7: If A ∈ N1
with rhs(A) = B(C) or rhs(A) = B(C(x)), then rhs1 (A) = BC. So, for every
A ∈ Na we have valH (A) = A1 A2 · · · An An+1 for some n ≥ 1, where Ai ∈ Nd
for 1 ≤ i ≤ n and An+1 ∈ Nc . Let ℓ(A) = n+1 (this is the length of the spine path
15

of A), A[i : j] = Ai Ai+1 · · · Aj , A[i :] = Ai · · · An An+1 , and A[: i] = A1 · · · Ai .
We define s(A) as the smallest number i ≥ 2 such that valG (A[i :]) = valG (B)
for some nonterminal B ∈ N of rank zero. This unique nonterminal B is denoted
with A′ . Moreover, let rA (x) = rhs(As(A)−1 ) be the right-hand side of As(A)−1 ∈
Nd . Hence, rA (x) is a tree of the form f (X1 , . . . , Xi−1 , x, Xi+1 , . . . , Xm ) for
X1 , . . . , Xi−1 , Xi+1 , . . . , Xm ∈ N , f ∈ Fm , m ≥ 1. With these notations, we
have valG (A[s(A) − 1 :]) = valG (rA (A′ )). Note that s(A), rA , and A′ are welldefined since valG (A[n + 1 :]) = valG (An+1 ) and An+1 has rank zero.
Example 6 (Continued) The corresponding SLP H has the following rules:
S → GA, C → BA, E → DC, G → HI, H → F B, I → DB
We have valH (S) = F BDBA. Moreover, valG (DBA) = f (f (a, a), f (a, a)) =
valG (E), but valG (BDBA) = f (a, f (f (a, a), f (a, a))) is not equal to one of the
trees valG (X) for a nonterminal X of rank zero. Hence, we have S ′ = E, s(S) =
3, and rS = rhs(B) = f (A, x).
Lemma 1 For every nonterminal A ∈ Na , we can compute s(A), rA and A′ in
polynomial time.
Proof We first compute the position s(A) as follows. Let B1 , . . . , Bk be a list
of all nonterminals of rank zero. We can compute the size ni = |valG (Bi )| by a
simple bottom-up computation. Let us assume w.l.o.g. that n1 ≤ n2 ≤ · · · ≤ nk .
Note that there can be only one position 1 ≤ si ≤ ℓ(A) (1 ≤ i ≤ k) on the spine
path of A such that the tree valG (A[si :]) has size ni . This position (if it exists) can
be found in polynomial time using binary search. Note that for a given position
1 ≤ s ≤ ℓ(A) we can compute the size of tree valG (A[s :]) in polynomial time by
first computing a TSLP for this tree (using the second statement in Proposition 1)
and then compute the size of the produced tree bottom-up. Once the positions
s1 , . . . , sk are computed, we can compute in polynomial time TSLPs for the trees
ti = valG (A[si :]). The position s(A) is the smallest si ≥ 2 such that ti is equal
to one of the trees valG (Bj ), and the latter can be checked in polynomial time by
Proposition 3. This also yields the nonterminal A′ . Finally, the right-hand side rA
can be computed by computing in polynomial time the symbol B ∈ N2 in valH (A)
at position s(A) − 1 by the first statement of Proposition 1. Then, rA = rhs(B).
Lemma 2 For all A, B ∈ Na and all 1 ≤ i < s(A), 1 ≤ j < s(B), the following
two conditions are equivalent:
(i) valG (A[i :]) = valG (B[j :])
(ii) valH (A[i : s(A) − 2]) = valH (B[j : s(B) − 2]) and rA (A′ ) = rB (B ′ ).
Proof Clearly, (ii) implies (i). Now assume that valG (A[i :]) = valG (B[j :])
holds. Let valH (A) = A1 A2 · · · An An+1 and valH (B) = B1 B2 · · · Bm Bm+1 . By
16

induction on i and j, we show that valH (A[i : s(A) − 2]) = valH (B[j : s(B) − 2])
and rA (A′ ) = rB (B ′ ).
Case 1. i = s(A) − 1. By the definition of s(A), this implies that the tree
valG (A[i :]) has the form f (valG (X1 ), . . . , valG (Xk )), where f ∈ Fk , k ≥ 1,
and X1 , . . . , Xk are nonterminals of rank zero. Hence,
valG (B[j :]) = f (valG (X1 ), . . . , valG (Xk )).
But this implies that valG (B[j + 1 :]) is equal to one of the trees valG (Xl ). We
therefore get j = s(B) − 1. Thus, valH (A[i : s(A) − 2]) = ε = valH (B[j :
s(B) − 2]). Moreover, valG (rA (A′ )) = valG (A[s(A) − 1 :]) = valG (B[s(B) − 1 :
]) = valG (rB (B ′ )). Since G is reduced, we get rA (A′ ) = rB (B ′ ).
Case 2. j = s(B) − 1. This case is symmetric to Case 1.
Case 3. i < s(A) − 1 and j < s(B) − 1. We claim that Ai = Bj . If Ai 6= Bj , then,
since G is reduced, we have rhs(Ai ) 6= rhs(Bj ). With valG (A[i :]) = valG (B[j :]),
this implies that each of the trees valG (A[i + 1 :]) and valG (B[j + 1 :]) is equal to
a tree of the form valG (X) for X a nonterminal of rank zero. But this contradicts
i + 1 < s(A) as well as j + 1 < s(B). Hence, we have Ai = Bj . Moreover,
rhs(Ai ) = rhs(Bj ) implies with valG (A[i :]) = valG (B[j :]) that valG (A[i + 1 :
]) = valG (B[j + 1 :]). We can now conclude with induction.

Consider a valid sequence γ ∈ (L ∪ R ∪ M )∗ for G. We can uniquely factorize γ
as
γ = γ1 (A1 , k1 , B1 )γ2 (A2 , k2 , B2 ) · · · γn−1 (An−1 , kn−1 , Bn−1 )γn ,
(4)
where γi ∈ (L ∪ R)∗ (1 ≤ i ≤ n) and (Ai , ki , Bi ) ∈ M (1 ≤ i ≤ n − 1). To
simplify the notation, let us set B0 = S. Hence, every γi is either empty or a
valid Bi−1 -sequence for the SLP H, and we have defined the position pos(γi ) in
the string valH (Bi−1 ) according to Section 6. It is easy to modify our traversal
algorithms from the previous section such that for every 1 ≤ i ≤ n we store in the
sequence γ also the nonterminal Bi−1 and the number pos(γi ) right after γi (if γi 6=
ε), i.e., just before (Ai , ki , Bi ). The number pos(γi ) has to be incremented (resp.,
decremented) each time one moves down (resp., up) in the spine path for Bi−1 .
We will not explicitly write these nonterminals and positions in valid sequences in
order do not complicate the notation.
We would like to use Lemma 2 for equality checks. To do this, we have to
assume that pos(γi ) < s(Bi−1 ) in (4) for every 1 ≤ i ≤ n with γi 6= ε (this
corresponds to the assumptions 1 ≤ i < s(A) and 1 ≤ j < s(B) in Lemma 2).
To do this, we have to modify our traversal algorithms from the previous section as
follows: Assume that the current valid sequence is γ from (4). As remarked above,
we store the numbers pos(γi ) right after each γi . Assume that the final number
pos(γn ) has reached the value s(Bn−1 ) − 1 and we want to move to the ith child
of the current node. We proceed as in Algorithm 4 with one exception: In case (ii)
(Section 7) we would increase pos(γi ) to s(Bn−1 ). To avoid this, we start a new
17

′
). Note that by the definition of
valid sequence for the root of the tree valG (Bn−1
′
Bn−1 , this is exactly the tree rooted at the ith child of the node represented by γ.
′
). Therefore, we continue
So, we can continue the traversal in the tree valG (Bn−1
′
with the sequence γ | root(Bn−1 ), where | is a separator symbol, and the rootfunction is defined at the end of Section 7. The navigation to the parent node can
be easily adapted as well. The only new case that we have to add to Algorithm 3 is
for γ = α | β, where β ∈ (L ∪ R)+ . In that case, we compute β ′ = left(β) and
return α | β ′ if β ′ is not undefined, and α otherwise. Thus, the separator symbol |
is treated in the same way as triples from M .
Let us now consider two sequences γ1 and γ2 (that may contain the separator
symbol | as explained in the previous paragraph). Let vi be the node of val(G)
represented by γi and let ti be the subtree of val(G) rooted in vi . We want to
check in time O(1) whether t1 = t2 . We can first compute in time O(1) the
labels label(γ1 ) and label(γ2 ) of the nodes v1 and v2 , respectively. In case one of
these labels belongs to F0 (i.e., one of the nodes v1 , v2 is a leaf) we can easily
determine whether t1 = t2 . Hence, we can assume that neither v1 nor v2 is a leaf.
In particular we can assume that γ1 6= ε 6= γ2 (recall that ε is a valid sequence
only in case val(G) consists of a single node) and that neither γ1 nor γ2 ends with
a triple from M . Let us factorize γi as γi = αi βi , where βi is the maximal suffix
of γi that belongs to (L ∪ R)∗ . Hence, we have β1 6= ε 6= β2 .
Assume that βi is a valid Ci -sequence of H, and that ni = pos(βi ). Thus, the
suffix βi represents the ni -th leaf of the derivation tree of H with root Ci . Recall
that we store Ci and ni at the very end of our sequence γi . Hence, we have constant
time access to Ci and ni . We have Ci ∈ Na and ni < s(Ci ). With the notation
introduced before, we get ti = valG (Ci [ni :]). Since n1 < s(C1 ) and n2 < s(C2 ),
Lemma 2 implies that t1 = t2 if and only if the following two conditions hold:

(i) valH (C1 [n1 : s(C1 ) − 2]) = valH (C2 [n2 : s(C2 ) − 2]) and
(ii) rC1 (C1′ ) = rC2 (C2′ ).
Condition (ii) can be checked in time O(1), since we can precompute in polynomial
time rA and A′ for every A ∈ Na by Lemma 1. So, let us concentrate on condition
(i). First, we check whether s(C1 ) − n1 = s(C2 ) − n2 . If not, then the lengths
of valH (C1 [n1 : s(C1 ) − 2]) and valH (C2 [n2 : s(C2 ) − 2]) differ and we cannot
have equality. Hence, assume that k := s(C1 ) − 1 − n1 = s(C2 ) − 1 − n2 .
Let ℓ be the length of the longest common suffix of valH (C1 [: s(C1 ) − 2]) and
valH (C2 [: s(C2 ) − 2]). Then, it remains to check whether k ≤ ℓ. Clearly, in
space O(|G|) we cannot store explicitly all these lengths ℓ for all C1 , C2 ∈ Na .
Instead, we precompute in polynomial time a modified Patricia tree for the set of
strings wA := valH (A[: s(A)− 2])rev $ ($ is a new symbol that is appended in order
make the set of strings prefix-free and wrev is the string w reversed) for A ∈ Na .
Then, we need to compute in O(1) time the length of the longest common prefix
for two of these strings wA and wB . Recall that the Patricia tree for a set of strings
w1 , . . . , wn is obtained from the trie for the prefixes of the wi by eliminating nodes
18

bb

0

ba

a

•
•

b

A

B

C

•

A

$a

b$

$

3

$a

•

b$

D

E

2
B

3

C
D

E

Figure 4: The Patricia tree (left) and the modified Patricia tree (right) for Example 7

with a single child. But instead of labeling edges of the Patricia tree with factors of
the wi , we label every internal node with the length of the strings that leads from
the root to the node. Let us give an example instead of a formal definition:
Example 7 Consider the strings wA = abba$, wB = abbb$, wC = ba$, wD =
baba$ and wE = babb$. Figure 4 shows their Patricia tree (left) and the modified
Patricia tree (right).
Since our modified Patricia tree has |Na | many leaves (one for each A ∈ Na ) and
every internal node has at least two children, we have at most 2|Na | − 1 many
nodes in the tree and every internal node is labeled with an (log |t|)-bit number
(note that the length of every string valH (A) (A ∈ Na ) is bounded by |t|. Hence,
on the word RAM model, we can store the modified Patricia tree in space O(|G|).
Finally, the length of the longest common prefix of two string wA and wB can be
obtained by computing the lowest common ancestor of the two leaves corresponding to the strings wA and wB in the Patricia tree. The number stored in the lowest
common ancestor is the length of the longest common prefix of wA and wB . Using
a data structure for computing lowest common ancestors in time O(1) [1, 23], we
obtain an O(1)-time implementation of subtree equality checking. Finally, from
Proposition 1 it follows that the modified Patricia tree for the strings wA (A ∈ Na )
can be precomputed in polynomial time.
The following theorem is the main result of this section:
Theorem 2 Given a monadic TSLP G for a tree t = val(G) we can compute in
polynomial time on a word RAM with register length O(log |t|) a data structure
of size O(|G|) that allows to do the following computations in time O(1), where γ
and γ ′ are valid sequences (as modified in this section) that represent the tree nodes
v and v ′ , respectively: (i) Compute the valid sequence for the parent node of v,
(ii) compute the valid sequence for the ith child of v, and (iii) check whether the
subtrees rooted in v and v ′ are equal.

19

9 Discussion
We have presented a data structure to traverse grammar-compressed ranked trees
with constant delay and to check equality of subtrees. The solution is based on the
ideas of [10] and the fact that next link queries can be answered in time O(1) (after
linear time preprocessing). It would be interesting to develop an efficient implementation of the technique. Next link queries can be implemented in many different ways. One solution given in [10] is based on a variant of the lowest common
ancestor algorithm due to Schieber and Vishkin [23] (described in [13]). Another
solution is to use level-ancestor queries (together with depth-queries), as are available in implementation of succinct tree data structures (e.g., the one of Navarro and
Sadakane [22]). Another alternative is to store the first-child/next-sibling encoded
binary tree of the original tries. The first-child/next-sibling encoding is defined for
ordered trees. In our situation, we have to answer next-link queries for the tries
TL (a) and TR (a) for a ∈ Σ, which are unordered. Hence we order the children of
a node in an arbitrary way. Then the next link of v1 above v2 is equal to the lowest
common ancestor of v2 and the last child of v1 in the original tree. This observation
allows to use simple and efficient lowest common ancestor data structures like the
one of Bender and Farach-Colton [1].
Recall that we used polynomial time preprocessing to built up our data structure
for subtree equality checks. It remains to come up with a more precise time bound.
We already argued that the problem is at least as difficult as checking equality
of SLP-compressed strings, for which the best known algorithm is quadratic. It
would be interesting, to show that our preprocessing has the same time complexity
as checking equality of SLP-compressed strings.

References
[1] M. A. Bender and M. Farach-Colton. The LCA problem revisited. In Proceedings of LATIN 2000, volume 1776 of Lecture Notes in Computer Science,
pages 88–94. Springer, 2000.
[2] P. Bille, I. L. Gørtz, G. M. Landau, and O. Weimann. Tree compression with
top trees. Information and Computation, 243: 166–177, 2015.
[3] P. Bille, G. M. Landau, R. Raman, K. Sadakane, S. R. Satti, and O. Weimann.
Random access to grammar-compressed strings and trees. SIAM Journal on
Computing, 44(3)513–539:, 2015.
[4] M. Bousquet-Mélou, M. Lohrey, S. Maneth, and E. Noeth. XML compression
via DAGs. Theory of Computing Systems, 2014. DOI 10.1007/s00224-0149544-x.
[5] G. Busatto, M. Lohrey, and S. Maneth. Efficient memory representation of
XML document trees. Information Systems, 33(4–5):456–474, 2008.
20

[6] J. Cai and R. Paige. Using multiset discrimination to solve language
processing problems without hashing. Theoretical Computer Science,
145(1&2):189–228, 1995.
[7] M. Charikar, E. Lehman, A. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran,
A. Sahai, and A. Shelat. The smallest grammar problem. IEEE Transactions
on Information Theory, 51(7):2554–2576, 2005.
[8] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, C. Löding,
S. Tison, and M. Tommasi. Tree automata techniques and applications. Available at http://tata.gforge.inria.fr/, 2007.
[9] O. Delpratt, R. Raman, and N. Rahman. Engineering succinct DOM. In Proceedings of EDBT, volume 261 of ACM International Conference Proceeding
Series, pages 49–60, ACM, 2008.
[10] L. Gasieniec, R. M. Kolpakov, I. Potapov, and P. Sant.
Real-time
traversal in grammar-based compressed files.
In Proceedings of
DCC 2005, page 458, IEEE Computer Society, 2005.
Availabe at
http://www.csc.liv.ac.uk/˜leszek/papers/dcc05.ps.gz.
[11] L. Hübschle-Schneider and Rajeev Raman. Tree compression with top trees
revisited. In Proceedings of SEA 2015, volume 9125 of Lecture Notes in
Computer Science, pages 15–27. Springer, 2015. Long version at arXiv.org,
2015., http://arxiv.org/abs/1506.04499.
[12] D. Hucke, M. Lohrey, and E. Noeth. Constructing small tree grammars and
small circuits for formulas. In Proceedings of FSTTCS 2014, volume 29 of
LIPIcs, pages 457–468. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2014.
[13] D. Gusfield. Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. Cambridge University Press, 1997.
[14] A. Jeż. Faster fully compressed pattern matching by recompression. ACM
Transactions on Algorithms, 11(3):20:1–20:43, 2015.
[15] A. Jeż and M. Lohrey. Approximation of smallest linear tree grammars. In
Proceedings of STACS 2014, volume 25 of LIPIcs, pages 445–457. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2014.
[16] M. Lohrey. Algorithmics on SLP-compressed strings: A survey. Groups
Complexity Cryptology, 4(2):241–299, 2012.
[17] M. Lohrey and S. Maneth. The complexity of tree automata and XPath on
grammar-compressed trees. Theoretical Computer Science, 363(2):196–210,
2006.

21

[18] M. Lohrey, S. Maneth, and R. Mennicke. XML tree structure compression
using RePair. Information Systems, 38(8):1150–1167, 2013.
[19] M. Lohrey, S. Maneth, and M. Schmidt-Schauß. Parameter reduction and
automata evaluation for grammar-compressed trees. Journal of Computer
and Systems Science, 78(5):1651–1669, 2012.
[20] S. Maneth and T. Sebastian. Fast and tiny structural self-indexes for XML.
CoRR, abs/1012.5696, 2010.
[21] S. Maneth and T. Sebastian. XPath node selection over grammar-compressed
trees. In Proceedings of TTATT 2013, Electronic Proceedings in Theoretical
Computer Science 134, pages 38–48, 2013.
[22] G. Navarro and K. Sadakane. Fully functional static and dynamic succinct
trees. ACM Transactions on Algorithms, 10(3):16, 2014.
[23] B. Schieber and U. Vishkin. On Finding Lowest Common Ancestors: Simplification and Parallelization. SIAM Journal on Computing, 17(6):1253–1262,
1988.

22

