FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree

An ordered dag (directed acyclic graph) is a triple $G=(V,\gamma ,\iota )$, where $V$ is a finite set of nodes, $\gamma :V\to V^{\ast }$ is the child-function, the relation $E:=\{(u,v):u,v\in V,v\text{ occurs in }\gamma (u)\}$ is acyclic, and $\iota \in V$ is the initial node. The size of $G$ is $|G|={\sum }_{v\in V}(1+|\gamma (v)|)$. A node $v\in V$ with $|\gamma (v)|=0$ is called a leaf.

A path in $G$ (from $v_0$ to $v_n$) is a sequence $p=v_0{i}_1{v}_1{i}_2\mathrm{\cdots }{v}_{n-1}{i}_n{v}_n\in V{(\mathbb{N}V)}^{\ast }$ such that $1\le i_k\le |\gamma (v_{k-1})|$ for all $k\in [n]$. The length of this path $p$ is $n$ (we may have $n=0$ in which case $p=v_0$) and we also call $p$ a $v_0$-to-$v_n$ path or $v_0$-path if the end point $v_n$ is not important. An $\iota$-path is also called an initial path. We extend this notation to subsets of $V$ in the obvious way, e.g., for $A,B\subseteq V$ and $v\in V$ we talk about $A$-to-$v$ paths, $A$-to-$B$ paths, $A$-to-leaf paths (where “leaf” refers to the set of all leaves of the dag), initial-to-leaf paths, etc. For a $v_0$-to-$v_1$ path $p=p^{\prime }{v}_1$ and a $v_1$-to-$v_2$ path $q=v_1{q}^{\prime }$ we define the $v_0$-to-$v_2$ path $pq=p^{\prime }{v}_1{q}^{\prime }$ (note that if we just concatenate $p$ and $q$ as words, then we have to replace the double occurrence $v_1{v}_1$ by $v_1$ to obtain $pq$). We say that the path $p$ is a prefix of the path $q$ if there is a path $r$ such that $q=qr$.

Since we consider ordered dags, there is a natural lexicographical ordering on all $v$-paths (i.e., all paths that start in the same node $v$). More precisely, for two different $v$-paths $p$ and $q$ we write if either $p$ is a proper prefix of $q$ or we can write $p$ and $q$ as $p=ri{p}^{\prime }$, $q=rj{q}^{\prime }$ for paths $r,p^{\prime },q^{\prime }$ and $i,j\in \mathbb{N}$ with .

A signature $ℛ$ is a finite set consisting of relation symbols $r_i$ ($i\in I$) and constant symbols $c_j$ ($j\in J$). Each relation symbol $r_i$ has an associated arity ${\alpha }_i$. A structure over the signature $ℛ$ is a tuple $𝒰=(U,{(R_i)}_{i\in I},{(u_j)}_{j\in J})$, where $U$ is a finite non-empty set (the universe of $𝒰$), $R_i\subseteq U^{{\alpha }_i}$ is the relation associated with the relation symbol $r_i$, and $u_j\in U$ is the constant associated with the constant symbol $c_j$. Note that we restrict to finite structures. If the structure $𝒰$ is clear from the context, we will identify $R_i$ ($u_j$, respectively) with the relation symbol $r_i$ (the constant symbol $c_j$, respectively). Sometimes, when we want to refer to the universe $U$, we will refer to $𝒰$ itself. For instance, we write $a\in 𝒰$ for $ua\in U$, or $f:[n]\to 𝒰$ for a function $f:[n]\to U$. The size $|𝒰|$ of $𝒰$ is $|U|+{\sum }_{i\in I}{\alpha }_i\cdot |R_i|$. As usual, a constant $a\in 𝒰$ may be replaced by the unary relation $\{a\}$. Thus, in the following, we will only consider signatures without constant symbols, except when we explicitly introduce constants. Let $ℛ=\{r_i:i\in I\}$ be such a signature (we call it a relational signature) and let $𝒰=(U,{(R_i)}_{i\in I})$ be a structure over $ℛ$ (we call it a relational structure). For relational structures ${𝒰}_1$ and ${𝒰}_2$ over the signature $ℛ$, we write ${𝒰}_1\simeq {𝒰}_2$ to denote that ${𝒰}_1$ and ${𝒰}_2$ are isomorphic. A substructure of $𝒰=(U,{(R_i)}_{i\in I})$ is a structure $(V,{(S_i)}_{i\in I})$ such that $V\subseteq U$ and $S_i\subseteq R_i$ for all $i\in I$. The substructure of $𝒰$ induced by $V\subseteq U$ is $(V,{(R_i\cap V^{{\alpha }_i})}_{i\in I})$. We define the undirected graph $𝒢(𝒰)=(U,E)$ (the so-called Gaifman graph of $𝒰$), where $E$ contains an edge $(a,b)$ if and only if there is a binary relation $R_i$ ($i\in I$) and a tuple $(a_1,\mathrm{\dots },a_{{\alpha }_i})\in R_i$ with $\{a,b\}\subseteq \{a_1,\mathrm{\dots },a_{{\alpha }_i}\}$. The degree of $𝒰$ is the maximal degree of a node in $𝒢(𝒰)$. If $𝒰$ has degree at most $d$, we also say that $𝒰$ is a degree-$d$ bounded structures.

We use first-order logic (FO) over finite relational structures; see [15] for a detailed introduction and the full version [43] for some standard notations. For an FO-formula $\psi (x_1,\mathrm{\dots },x_k)$ over the signature $ℛ$ with free variables $x_1,\mathrm{\dots },x_k$ and a relational structure $𝒰=(U,{(R_i)}_{i\in I})$ over $ℛ$ and $a_1,\mathrm{\dots },a_k\in U$, we write $𝒰\vDash \psi (a_1,\mathrm{\dots },a_k)$ if $\psi$ is true in $𝒰$ when the variable $x_i$ is set to $a_i$ for all $i\in [k]$. Hence, an FO-formula $\psi (x_1,\mathrm{\dots },x_k)$ can be interpreted as an FO-query that, for a given structure $𝒰$, defines a result set

The quantifier rank $\mathrm{𝗊𝗋}(\psi )$ of an FO-formula $\psi$ is inductively defined as follows: $\mathrm{𝗊𝗋}(\psi )=0$ if $\psi$ contains no quantifiers, $\mathrm{𝗊𝗋}(\neg \psi )=\mathrm{𝗊𝗋}(\psi )$, $\mathrm{𝗊𝗋}({\psi }_1\wedge {\psi }_2)=\mathrm{𝗊𝗋}({\psi }_1\vee {\psi }_2)=\max \{\mathrm{𝗊𝗋}({\psi }_1),\mathrm{𝗊𝗋}({\psi }_2)\}$ and $\mathrm{𝗊𝗋}(\forall x\psi )=\mathrm{𝗊𝗋}(\exists x\psi )=1+\mathrm{𝗊𝗋}(\psi )$.

In the rest of the paper, we assume that the signature only contains relation symbols of arity at most two. It is folklore that FO model checking and FO-query enumeration over arbitrary signatures can be reduced to this case; see the full version [43] for a possible construction. This construction can be carried out in linear time (in the size of the formula and the structure) and it increase the degree of the structure as well as the quantifier rank of the formula by at most one.

Let us fix a relational signature $ℛ$ (containing only relation symbols of arity at most two) and let $𝒰=(U,{(R_i)}_{i\in I})$ be a structure over this signature. We say that $𝒰$ is connected, if its Gaifman graph $𝒢(𝒰)$ is connected. The distance between elements $a,b\in U$ in the graph $𝒢(𝒰)$ is denoted by ${\mathrm{𝖽𝗂𝗌𝗍}}_{𝒰}(a,b)$ (it can be $\mathrm{\infty }$). For subsets $A,B\subseteq U$ we define ${\mathrm{𝖽𝗂𝗌𝗍}}_{𝒰}(A,B)=\min \{{\mathrm{𝖽𝗂𝗌𝗍}}_{𝒰}(a,b):a\in A,b\in B\}$. For two partial tuples (of any arity) $t,t^{\prime }$ over $U$ let ${\mathrm{𝖽𝗂𝗌𝗍}}_{𝒰}(t,t^{\prime })={\mathrm{𝖽𝗂𝗌𝗍}}_{𝒰}(ran(t),ran(t^{\prime }))$.

Fix a constant $d\ge 2$. We will only consider degree-$d$ bounded structures in the following. Let us fix such a structure $𝒰$ (over the relational signature $ℛ$). Take additional constant symbols $c_1,c_2,\mathrm{\dots }$ called sphere center constants. For an $r\ge 1$ and a partial $k$-tuple $t:[k]\to 𝒰$ we define the $r$-sphere ${𝒮}_{𝒰,r}(t)=\{b\in 𝒰:{\mathrm{𝖽𝗂𝗌𝗍}}_{𝒰}(t,b)\le r\}$. The $r$-neighborhood ${𝒩}_{𝒰,r}(t)$ of $t$ is obtained by taking the substructure of $𝒰$ induced by ${𝒮}_{𝒰,r}(t)$ and then adding every node $t(i)$ ($i\in dom(t)$) as the interpretation of the sphere center constant $c_i$. Hence, it is a structure over the signature $ℛ\cup \{c_i:i\in dom(t)\}$. The $r$-neighborhood of a $k$-tuple has at most $k\cdot {\sum }_{i=0}^r{d}^i\le k\cdot d^{r+1}$ elements (here, the inequality holds since we assume $d\ge 2$).

We use the above definitions also for a single element $a\in 𝒰$ in place of a tuple $t$; formally $a$ is identified with the $1$-tuple $t$ such that $t(1)=a$. We are mainly interested in $r$-spheres and $r$-neighborhoods of complete $k$-tuples, but the corresponding notions for partial $k$-tuples will be convenient later. We also drop the subscript $𝒰$ from the above notations if this does not cause any confusion.

A $(k,r)$-neighborhood type is an isomorphism type for the $r$-neighborhood of a complete $k$-tuple in a degree-$d$ bounded structure. More precisely, we can define a $(k,r)$-neighborhood type as a degree-$d$ bounded structure $ℬ$ over the signature $ℛ\cup \{c_1,\mathrm{\dots },c_k\}$ such that

• $\mathrm{■}$

  the universe of $ℬ$ is of the form $[\mathrm{\ell }]$ for some $\mathrm{\ell }\le k\cdot d^{r+1}$ and

• $\mathrm{■}$

  for every $j\in [\mathrm{\ell }]$ there is $i\in [k]$ such that ${\mathrm{𝖽𝗂𝗌𝗍}}_{ℬ}(a_i,j)\le r$, where, for every $i\in [k]$, $a_i$ is the interpretation of the sphere center constant $c_i$.

From each isomorphism class of $(k,r)$-neighborhood types we select a unique representative and write ${𝒯}_{k,r}$ for the set of all selected representatives. Then, for every $k$-tuple $\overline{a}\in {𝒰}^k$ there is a unique $ℬ\in {𝒯}_{k,r}$ such that ${𝒩}_{𝒰,r}(\overline{a})\simeq ℬ$; we call it the $(k,r)$-neighborhood type of $\overline{a}$ and say that $\overline{a}$ is a $ℬ$-tuple. In case $k=1$ we speak of $ℬ$-nodes instead of $ℬ$-tuples, write ${𝒯}_r$ for ${𝒯}_{1,r}$ and call its elements $r$-neighborhood types instead of $(1,r)$-neighborhood types.

For every $(k,r)$-neighborhood type $ℬ\in {𝒯}_{k,r}$ there is an FO-formula ${\psi }^{ℬ}(x_1,\mathrm{\dots },x_k)$ such that for every degree-$d$ bounded structure $𝒰$ and every $k$-tuple $\overline{a}\in {𝒰}^k$ we have $𝒰\vDash {\psi }^{ℬ}(\overline{a})$ if and only if $\overline{a}$ is a $ℬ$-tuple.

FO-query enumeration is the following problem: Given an FO-formula $\varphi (x_1,\mathrm{\dots },x_k)$ over some signature $ℛ$ and a relational structure $𝒰$ over $ℛ$, we want to enumerate all tuples from $\varphi (𝒰)$ in some order and without repetitions, i.e., we want to produce a sequence $(t_1,\mathrm{\dots },t_n,t_{n+1})$ with $\{t_1,\mathrm{\dots },t_n\}=\varphi (𝒰)$, $|\varphi (𝒰)|=n$ and $t_{n+1}=\mathrm{𝖤𝖮𝖤}$ is the end-of-enumeration marker. An algorithm for FO-query enumeration starts with a preprocessing phase in which no output is produced, followed by an enumeration phase, where the elements $t_1,t_2,\mathrm{\dots },t_n,t_{n+1}$ are produced one after the other. The running time of the preprocessing phase is called the preprocessing time, and the delay measures the maximal time between the computation of two consecutive outputs $t_i$ and $t_{i+1}$ for every $i\in [n]$.

Usually, one restricts the input structure $𝒰$ to some subclass ${𝖢}_d$ of relational structures that is defined by some parameter $d$ (in this paper, ${𝖢}_d$ is the class of degree-$d$ bounded structures). We say that an algorithm for FO-query enumeration for ${𝖢}_d$ has linear preprocessing and constant delay, if its preprocessing time is $𝒪(|𝒰|\cdot f(d,|\varphi |))$ and its delay is $𝒪(f(d,|\varphi |))$ for some computable function $f$. This complexity measure where the query $\varphi$ is considered to be constant and the running time is only measured in terms of the data, i.e., the size of the relational structure, is also called data complexity. In data complexity, linear preprocessing and constant delay is considered to be optimal (since we assume that the relational structure has to be read at least once). As mentioned in the introduction, FO-query enumeration can be solved with linear preprocessing and constant delay for several classes ${𝖢}_d$.

For proving upper bounds in data complexity, we often have to argue that certain computational tasks can be performed in time $f(\cdot )$ (or $|𝒰|\cdot f(\cdot ))$ for some function $f$. In these cases, without explicitly mentioning this in the remainder, $f$ will always be a computable function (actually, $f$ will be elementary, i.e., bounded by an exponent tower of fixed height). The arguments for $f$ will only depend on the parameter $d$ and the formula size $|\varphi |$.

The special feature of this work is that we consider FO-query enumeration in the setting where the relational structure $𝒰$ is not given explicitly, but in a potentially highly compressed form, and our enumeration algorithm must handle this compressed representation rather than decompressing it. Then the structure size $|𝒰|$ will be replaced by the size of the compressed representation of $𝒰$ in all time bounds. This aspect shall be explained in detail in Section 4.

We use the standard RAM model with uniform cost measure as our model of computation. We will make some further restrictions for the register length tailored to the compressed setting in Section 4.2.

Let us fix a $(k,r)$-neighborhood type $ℬ$ and a consistent factorization $\mathrm{\Lambda }=({ℬ}_1,{\sigma }_1,\mathrm{\dots },{ℬ}_m,{\sigma }_m)$ of $ℬ$. By Lemmas 3 and 3, it suffices to enumerate (with linear preprocessing and constant delay) the set of all $\overline{a}\in {𝒰}^m$ that are admissible for $\mathrm{\Lambda }$. In the preprocessing phase we compute

• $\mathrm{■}$

  for every $i\in [m]$ a list $L_i$ containing all ${ℬ}_i$-nodes from $𝒰$ and

• $\mathrm{■}$

  for every $a\in L_i$ an isomorphism ${\pi }_a:{ℬ}_i\to {𝒩}_{\rho }(a)$.

It is straightforward to compute these data in time $|𝒰|\cdot f(d,|\varphi |)$ (in Section 5, where we deal with the more general SLP-compressed case, this is more subtle). We classify each list $L_i$ as being short if $|L_i|\le k\cdot d^{2\rho +2r+2}$ and as being long otherwise. Without loss of generality, we assume that, for some $0\le q\le m$ the lists $L_1,\mathrm{\dots },L_q$ are short and the lists $L_{q+1},\mathrm{\dots },L_m$ are long (note that this includes the cases that all lists are short or all lists are long).

Our enumeration procedure maintains a stack of the form $a_1{a}_2\mathrm{\cdots }{a}_{\mathrm{\ell }}$ with $0\le \mathrm{\ell }\le m$ and $a_i\in L_i$ for all $i\in [\mathrm{\ell }]$. Note that if $\mathrm{\ell }=0$, then we have the empty stack $\epsilon$. Such a stack is called admissible for $\mathrm{\Lambda }$ (or just admissible), if for all $i,i^{\prime }\in [\mathrm{\ell }]$ with $i\ne i^{\prime }$ and all $j\in dom({\sigma }_i)$ and $j^{\prime }\in dom({\sigma }_{i^{\prime }})$ we have ${\mathrm{𝖽𝗂𝗌𝗍}}_{𝒰}({\pi }_{a_i}({\sigma }_i(j)),{\pi }_{a_{i^{\prime }}}({\sigma }_{i^{\prime }}(j^{\prime })))>2r+1$. Note that the empty stack as well as every stack $a_1$ with $a_1\in L_1$ are admissible.

The general structure of our enumeration algorithm is a depth-first-left-to-right (DFLR) traversal over all admissible stacks $s$. For this, it calls the recursive procedure extend (shown as Algorithm 1) with the initial admissible stack $s=\epsilon$. Note that whenever extend$(s)$ is called, holds. It is clear that the call extend$(\epsilon )$ triggers the enumeration of all admissible stacks $a_1{a}_2\mathrm{\cdots }{a}_m$. In an implementation one would store $s$ as a global variable.

Let us assume that we can check whether a stack $s$ is admissible in time $f(d,|\varphi |)$ (it is not hard to see that this is possible, and this aspect will anyway be discussed in detail for the compressed setting in Section 5). After the initial call extend$(\epsilon )$, the algorithm constructs an admissible stack $s$ with $|s|=q$ (or terminates) after time bounded in $d,k,r$ and $\rho$ (since the lists $L_1,\mathrm{\dots },L_q$ are short). If some $a\in L_{q+1}$ is non-admissible, i.e., the stack $sa$ is not admissible, then ${\mathrm{𝖽𝗂𝗌𝗍}}_{𝒰}(t_{a_i,{\sigma }_i},t_{a,{\sigma }_{q+1}})\le 2r+1$ and therefore $\mathrm{𝖽𝗂𝗌𝗍}(a_i,a)\le 2\rho +2r+1$ for some $i\in [q]$. Thus, the total number of non-admissible elements from $L_{q+1}$ can be bounded by a function of $d,k,r$ and $\rho$. Consequently, since $L_{q+1}$ is long, the algorithm necessarily finds some admissible $a\in L_{q+1}$ (or terminates) after time bounded in $d,k,r$ and $\rho$. From this observation, the following lemma can be obtained with moderate effort; see [43].

Let $A\in N$. A node $a\in \mathrm{𝗏𝖺𝗅}(A)$ can be uniquely represented by a pair $(p,v)$ such that $p$ is an $A$-path in $\mathrm{𝖽𝖺𝗀}(D)$ and one of the following two cases holds:

• $\mathrm{■}$

  $p$ ends in $B\in N\setminus \{A\}$ and $v\in {𝒰}_B\setminus ran({\tau }_B)$ is an internal node.¹¹1The nodes in $ran({\tau }_B)$, i.e., the contact nodes of ${𝒰}_B$, are excluded here, because they were already generated by some larger (with respect to the hierarchical order ${\succ }_D$) nonterminal.

• $\mathrm{■}$

  $p=A$ and $v\in {𝒰}_A$.

We call this the $A$-representation of $a$. The $S$-representations of the nodes of $\mathrm{𝗏𝖺𝗅}(S)=\mathrm{𝗏𝖺𝗅}(D)$ are also called $D$-representations. Note that if $(p,v)$ is the $D$-representation of a node then $v\in {𝒰}_A\setminus ran({\tau }_A)$ for some $A\in N$ (since $\mathrm{𝗋𝖺𝗇𝗄}(S)=0$). We will often identify a node of $\mathrm{𝗏𝖺𝗅}(A)$ with its $A$-representation; in particular when $A=S$. One may view a $D$-representation $(p,v)$ as a stack $pv$. In order to construct outgoing (or incoming) edges of $(p,v)$ in the structure $\mathrm{𝗏𝖺𝗅}(D)$, one only has to modify this stack at its end; see [43] for more details.

The apex condition implies a kind of locality in $\mathrm{𝗏𝖺𝗅}(D)$ that can be nicely formulated in terms of $D$-representations: If two nodes $a=(p,u)$ and $b=(q,v)$ have distance $\zeta$ in the graph $𝒢(\mathrm{𝗏𝖺𝗅}(D))$ then the prefix distance between $p$ and $q$ (which is the number of edges in $p$ and $q$ that do not belong to the longest common prefix of $p$ and $q$) is also at most $\zeta$. This property is exploited several times in the paper.

Based on $A$-representations, we can define a natural embedding of $\mathrm{𝗏𝖺𝗅}(B)$ into $\mathrm{𝗏𝖺𝗅}(A)$ in case $A{\succ }_{D}B$. Assume that $p$ is a non-empty $A$-to-$B$ path in $\mathrm{𝖽𝖺𝗀}(D)$ with $A\ne B$. Let us write $p=p^{\prime }CiB$ for some nonterminal $C$ (we may have $C=A$). Let $(B,\sigma )\in E_C$ be the unique reference that corresponds to the edge $(C,i,B)$ in $\mathrm{𝖽𝖺𝗀}(D)$. We then define the embedding ${\eta }_p:\mathrm{𝗏𝖺𝗅}(B)\to \mathrm{𝗏𝖺𝗅}(A)$ as follows, where $(q,v)$ is a node in $\mathrm{𝗏𝖺𝗅}(B)$ given by its $B$-representation so that $q$ is a $B$-path (recall that the path $pq$ is obtained by concatenating the paths $p$ and $q$; see Section 2.1):

We can extend this definition to the case $A=B$ (where $p=A$) by defining ${\eta }_p$ as the identity map on $\mathrm{𝗏𝖺𝗅}(A)=\mathrm{𝗏𝖺𝗅}(B)$. If $𝒰$ is the substructure of $\mathrm{𝗏𝖺𝗅}(B)$ induced by the set $U\subseteq \mathrm{𝗏𝖺𝗅}(B)$ then we write ${\eta }_p(𝒰)$ for the substructure of $\mathrm{𝗏𝖺𝗅}(A)$ induced by the set ${\eta }_p(U)$. Note that in general we do not have ${\eta }_p(𝒰)\simeq 𝒰$. For instance, if $𝒰=\mathrm{𝗏𝖺𝗅}(B)$ then in $\mathrm{𝗏𝖺𝗅}(A)$ there can be edges between contact nodes of $\mathrm{𝗏𝖺𝗅}(B)$ that are generated by a nonterminal $C$ with $C{\to }_{D}B$.

Recall the definition of the lexicographic order on the set of all $A$-paths of $\mathrm{𝖽𝖺𝗀}(D)$ for $A\in N$ (see Section 2.1). We define ${\mathrm{𝗅𝖾𝗑}}_A(p)$ as the position of $p$ in the lexicographically sorted list of all $A$-paths of $\mathrm{𝖽𝖺𝗀}(D)$, where we start with $0$ (i.e., ${\mathrm{𝗅𝖾𝗑}}_A(A)=0$; note that $A$ is the empty path starting in $A$ and hence the lexicographically smallest path among all $A$-paths). For ${\mathrm{𝗅𝖾𝗑}}_S(p)$ we just write $\mathrm{𝗅𝖾𝗑}(p)$. Later it will be convenient to represent the initial path component $p$ of a $D$-representation $(p,v)$ by the number $\mathrm{𝗅𝖾𝗑}(p)$ and call $(\mathrm{𝗅𝖾𝗑}(p),v)$ be the lex-representation of the node $a=(p,v)\in \mathrm{𝗏𝖺𝗅}(D)$. The number of initial paths in $\mathrm{𝖽𝖺𝗀}(D)$ can be bounded by $2^{𝒪(|D|)}$: the number of initial-to-leaf paths in $\mathrm{𝖽𝖺𝗀}(D)$ is bounded by $3^{|\mathrm{𝖽𝖺𝗀}(D)|/3}\le 3^{|D|/3}$ (this is implicitly shown in the proof of [11, Lemma 1]) and the number of all initial paths in $D$ is bounded by twice the number of initial-to-leaf paths in $D$. Hence, the numbers $\mathrm{𝗅𝖾𝗑}(p)$ have bit length $𝒪(|D|)$.

In the following sections we will develop an enumeration algorithm for the set of all tuples in $\varphi (\mathrm{𝗏𝖺𝗅}(D))$, where the SLP $D$ is part of the input. Recall that $\mathrm{𝗏𝖺𝗅}(D)$ may contain $2^{\mathrm{\Theta }(|D|)}$ many elements. In order to achieve constant delay, we therefore should set the register length in our algorithm to $\mathrm{\Theta }(|D|)$ so that we can store elements of $\mathrm{𝗏𝖺𝗅}(D)$. This is in fact a standard assumption for algorithms on SLP-compressed objects. For instance, when dealing with SLP-compressed strings, one usually assumes that registers can store positions in the decompressed string. We only allow additions, subtractions and comparisons on these $\mathrm{\Theta }(|D|)$-bit registers and these operations take constant time (since we assume the uniform cost measure). For registers of length $𝒪(\log |D|)$ we will also allow pointer operations.

Note that a $D$-representation $(p,v)$ needs $𝒪(|D|)$ many $𝒪(\log |D|)$-bit registers, whereas its lex-representation $(\mathrm{𝗅𝖾𝗑}(p),v)$ fits into two registers (one of length $𝒪(\log |D|)$).