Dynamic Direct Access of MSO Query Evaluation over Strings

For a set $A$, we denote by $2^A$ the power set of $A$. For $n\in \mathbb{N}$ with $n\ge 1$, we denote by $[n]$ the set $\{1,\mathrm{\dots },n\}$. We use $\mathrm{\Sigma }$ to denote a finite alphabet and ${\mathrm{\Sigma }}^{\ast }$ all strings (also called words) with symbols in $\mathrm{\Sigma }$. We will usually denote strings by $s,s^{\prime },s_i$ and similar. For every $s_1,s_2\in {\mathrm{\Sigma }}^{\ast }$, we write $s_1\cdot s_2$ (or $s_1{s}_2$ for short) for the concatenation of $s_1$ and $s_2$. If $s=a_1\mathrm{\dots }{a}_n\in {\mathrm{\Sigma }}^{\ast }$, we write $|s|=n$, that is, the length of $s$. We denote by $ϵ\in {\mathrm{\Sigma }}^{\ast }$ the string of $0$ length (i.e., $|ϵ|=0$), also called the empty string. For $s=a_1\mathrm{\dots }{a}_n\in {\mathrm{\Sigma }}^{\ast }$, we denote by $s[i,j]$ the substring $a_i\mathrm{\dots }{a}_j$, by $s[..i]$ the prefix $a_1\mathrm{\dots }{a}_i$ and by $s[i..]$ the suffix $a_i\mathrm{\dots }{a}_n$.

Given a finite set $X$ of variables and $n\in \mathbb{N}$, in this work we will heavily work with mappings of the form $\mu :X\to [n]$ as our outputs. We denote by $\mathrm{𝖽𝗈𝗆}(\mu )=X$ the domain of $\mu$ and by $\mathrm{𝗋𝖺𝗇𝗀𝖾}(\mu )=\{i\in [n]\mid \exists x\in X:\mu (x)=i\}$ the range of $\mu$. Further, we denote by ${\mu }_{\mathrm{\varnothing }}$ the empty mapping, which is the unique mapping such that $\mathrm{𝖽𝗈𝗆}(\mu )=\mathrm{\varnothing }$. In our examples, we will usually write $(x_1\mapsto i_1,\mathrm{\dots },x_{\mathrm{\ell }}\mapsto i_{\mathrm{\ell }})$ to denote the mapping $\mu :\{x_1,\mathrm{\dots },x_{\mathrm{\ell }}\}\to [n]$ such that $\mu (x_1)=i_1$, …, $\mu (x_{\mathrm{\ell }})=i_{\mathrm{\ell }}$. We also write $\mu \cup (x\mapsto i)$ with $x\notin \mathrm{𝖽𝗈𝗆}(\mu )$ for the mapping ${\mu }^{\prime }$ such that ${\mu }^{\prime }(x)=i$ and ${\mu }^{\prime }(y)=\mu (y)$ for every $y\in \mathrm{𝖽𝗈𝗆}(\mu )$.

Given a mapping $\mu :X\to [n]$, we define ${\mu }^{-1}:[n]\to 2^X$ as the set-inverse mapping of $\mu$, defined by ${\mu }^{-1}(i):=\{x\in X\mid \mu (x)=i\}$. Note that $i\in \mathrm{𝗋𝖺𝗇𝗀𝖾}(\mu )$ if, and only if, ${\mu }^{-1}(i)\ne \mathrm{\varnothing }$. Moreover, given a subset $Y\subseteq X$, we define the projection ${\pi }_Y(\mu )$ as the mapping ${\mu }^{\prime }:Y\to [n]$ such that ${\mu }^{\prime }(y)=\mu (y)$ for every $y\in Y$. Remark that if $Y=\mathrm{\varnothing }$, then ${\pi }_Y(\mu )={\mu }_{\mathrm{\varnothing }}$.

A variable-set automaton [24, 25, 4] (or vset automaton for short) is a tuple $𝒜=(Q,\mathrm{\Sigma },X,\mathrm{\Delta },q_0,F)$ where $Q$ is a finite set of states, $X$ is a finite set of variables, $q_0\in Q$ is an initial state, $F\subseteq Q$ is a finite set of states, and $\mathrm{\Delta }\subseteq Q\times \mathrm{\Sigma }\times 2^X\times Q$ is the transition relation. Given a string $s=a_1\mathrm{\dots }{a}_n$, a run $\rho$ of $𝒜$ over $s$ is a sequence:

such that $(q_{i-1},a_i,X_i,q_{i+1})\in \mathrm{\Delta }$ for every $i\le n$. We say that a run $\rho$ like (1) is valid if, and only if, ${\bigcup }_{i=1}^n{X}_i=X$ and $X_i\cap X_j=\mathrm{\varnothing }$ for every ; in other words, each variable in $X$ appears exactly once in $\rho$. If $\rho$ is valid, one can define the mapping ${\mu }_{\rho }:X\to [n]$ such that, for every $x\in X$, ${\mu }_{\rho }(x)=i$ where $i$ is the unique position that satisfies $x\in X_i$. As usual, we also say that a run $\rho$ like (1) is accepting if, and only if, $q_n\in F$. Then we define the output of $𝒜$ over a string $s$ as the set of mappings:

We define a partial run $\rho$ of $𝒜$ as a sequence of transitions $\rho :=p_0\stackrel{b_1/Y_1}{⟶}{p}_1\stackrel{b_2/Y_2}{⟶}\mathrm{\dots }\stackrel{b_n/Y_n}{⟶}{p}_n$ such that $(p_{i-1},b_i,Y_i,p_i)\in \mathrm{\Delta }$. We say that $\rho$ is a partial run from $p_0$ to $p_n$ over the string $b_1\mathrm{\dots }{b}_n$. Note that a run is also a partial run where we additionally assumed that $p_0=q_0$. We say that a partial run is valid if $Y_i\cap Y_j=\mathrm{\varnothing }$ for all $i\le j\le n$. We define the length of $\rho$ as $|\rho |=n$, and we make the convention that a single state $p_0$ is a partial run of length $0$. We define the set of variables $\mathrm{𝗏𝖺𝗋𝗌}(\rho )$ of a partial run $\rho$ as $\mathrm{𝗏𝖺𝗋𝗌}(\rho )={\bigcup }_{i=1}^n{Y}_i$. Given two partial runs $\rho =p_0\stackrel{b_1/Y_1}{⟶}\mathrm{\dots }\stackrel{b_n/Y_n}{⟶}{p}_n$ and $\sigma =r_0\stackrel{c_1/Z_1}{⟶}\mathrm{\dots }\stackrel{c_m/Z_m}{⟶}{r}_m$ such that $p_n=r_0$ we define the run $\rho \cdot \sigma$ as the concatenation of $\rho$ and $\sigma$, i.e., the partial run $\rho \cdot \sigma :=p_0\stackrel{b_1/Y_1}{⟶}\mathrm{\dots }\stackrel{b_n/Y_n}{⟶}{p}_n\stackrel{c_1/Z_1}{⟶}\mathrm{\dots }\stackrel{c_m/Z_m}{⟶}{r}_m$. Note that $|\rho \cdot \sigma |=|\rho |+|\sigma |$ and $\mathrm{𝗏𝖺𝗋𝗌}(\rho \cdot \sigma )=\mathrm{𝗏𝖺𝗋𝗌}(\rho )\cup \mathrm{𝗏𝖺𝗋𝗌}(\sigma )$.

We define the size $|𝒜$— of a vset automaton $𝒜=(Q,\mathrm{\Sigma },X,\mathrm{\Delta },q_0,F)$ as the number of states and transitions, so $|𝒜|:=|Q|+|\mathrm{\Delta }|$. In the following, we assume that all vset automata are trimmed, i.e., for every $q\in Q$ there exists a run $\rho$ that reaches $q$, and there exists a partial run $\sigma$ from $q$ to some state in $F$. We can make this assumption without loss of generality, since removing unreachable states can be done in time $𝒪(|𝒜|)$ without modifying $⟦𝒜⟧$.

In this paper, we usually refer to Monadic Second Order Logic (MSO) as our language for query evaluation; however, we will not define it formally here since we will use vset automata as an equivalent model for MSO. Precisely, when we refer to MSO, we mean MSO formulas of the form $\phi (x_1,\mathrm{\dots },x_n)$ over strings where $x_1,\mathrm{\dots },x_n$ are first-order open variables (see, e.g., [31] for a formal definition). Then, given a string $s$ as a logical structure, the MSO query evaluation problem refers to computing the set $⟦\phi (x_1,\mathrm{\dots },x_n)⟧(s):=\{\mu :\{x_1,\mathrm{\dots },x_n\}\to [|s|]\mid s,\mu \vDash \phi (x_1,\mathrm{\dots },x_n)\}$, which is the set of all first-order assignments (i.e., mappings) that satisfy $\phi$ over $s$. One can show that MSO over strings with first-order open variables is equally expressible to vset automata, basically, by following the same construction as for the Büchi-Elgot-Trakhtenbrot theorem [16] (see also [34]). Furthermore, vset automata (as defined here) are equally expressive to regular document spanners [24] for information extraction (see, e.g., [6, 34]). For this reason, we can use vset automata to define MSO queries, which also applies to the setting of document spanners, or any other query language equally expressive to MSO.

It is useful to consider vset automata that have no accepting runs that are not valid, so we make the following definition: we say that a vset automaton is functional if, and only if, for every $s\in {\mathrm{\Sigma }}^{\ast }$, every accepting run $\rho$ of $𝒜$ over $s$ is also valid. In [24], it was shown that there is an algorithm that, given a vset automaton $𝒜$, constructs in exponential time a functional vset automaton ${𝒜}^{\prime }$ of exponential size with respect to $𝒜$ such that $⟦𝒜⟧=⟦{𝒜}^{\prime }⟧$. We will thus restrict our analysis and algorithms to functional vset automata, since we can extend them to non-functional vset automata, incurring an exponential blow-up. One useful property of functional vset automata is that each state determines the variables that are assigned before reaching it in the following sense.

The lemma is standard in the literature for similar models, see e.g. [33]. We provide a short proof. By way of contradiction, suppose that there exists a state $q\in Q$ and two runs $\rho$ and ${\rho }^{\prime }$ that reach $q$ such that $\mathrm{𝗏𝖺𝗋𝗌}(\rho )\ne \mathrm{𝗏𝖺𝗋𝗌}({\rho }^{\prime })$. Given that $𝒜$ is trimmed, there exists a partial run $\sigma$ starting from $q$ that reaches some final state in $F$. Then the runs $\rho \cdot \sigma$ and ${\rho }^{\prime }\cdot \sigma$ are accepting. Since $𝒜$ is functional, both runs are also valid and should satisfy $\mathrm{𝗏𝖺𝗋𝗌}(\rho \cdot \sigma )=X=\mathrm{𝗏𝖺𝗋𝗌}({\rho }^{\prime }\cdot {\sigma }^{\prime })$. However, $\mathrm{𝗏𝖺𝗋𝗌}(\rho \cdot \sigma )\ne \mathrm{𝗏𝖺𝗋𝗌}({\rho }^{\prime }\cdot \sigma )$ which is a contradiction. $◀$

By Lemma 1, for every functional vset automaton $𝒜=(Q,\mathrm{\Sigma },X,\mathrm{\Delta },q_0,F)$ and every $q\in Q$ we define its sets of variables as $X_q$ to be the set as in the lemma. One consequence of Lemma 1 is that for every transition $(q,a,Y,q^{\prime })\in \mathrm{\Delta }$, we have $Y=X_{q^{\prime }}\backslash X_q$. In particular, there can only be $|\mathrm{\Sigma }|$ transitions for every pair $q,q^{\prime }$ of states such that overall $|\mathrm{\Delta }|=O({|Q|}^2\cdot \mathrm{\Sigma })$.

We will also restrict to unambiguous vset automata. We say that a vset automaton $𝒜=(Q,\mathrm{\Sigma },X,\mathrm{\Delta },q_0,F)$ is unambiguous if for every string $s\in {\mathrm{\Sigma }}^{\ast }$ and every $\mu \in ⟦𝒜⟧(s)$ there exists exactly one accepting run $\rho$ of $𝒜$ over $s$ such that $\mu ={\mu }_{\rho }$. It is well-known that for every vset automaton $𝒜$ one can construct an equivalent unambiguous functional vset automaton ${𝒜}^{\prime }$ of exponential size with respect to $𝒜$. Therefore, we can restrict our analysis to the class of unambiguous functional vset automaton without losing expressive power. Both are standard assumptions in the literature for MSO query evaluation and have been used to find efficient enumeration algorithms for computing $⟦𝒜⟧(s)$, see e.g. [25, 38, 34].

We work with the usual RAM model with unit costs and logarithmic size registers, see e.g. [27]. All data structures that we will encounter in our algorithms will be of polynomial size, so all addresses and pointers will fit into a constant number of registers. Also, all atomic memory operations like random memory access and following pointers can be performed in constant time. The numbers we consider will be of value at most ${|s|}^{|X|}$ where $X$ is the variable set of the automaton we consider. Thus, all numbers can be stored in at most $|X|$ memory cells and arithmetic operations on them can be performed in time $O({|X|}^2)$ naively¹¹1We remark that there are better algorithms for arithmetic operations, but we will not follow this direction here. If the reader is willing to use faster algorithms for multiplication and addition, then in all runtime bounds below the factor ${|X|}^2$ can be be reduced accordingly.. In the sequel, we use $\omega$ to denote the exponent for matrix multiplication.

Let $𝒜=(Q,\mathrm{\Sigma },X,\mathrm{\Delta },q_0,F)$ be a vset automaton and let $s=a_1\mathrm{\dots }{a}_n$ be a string of length $n$. Assume that $X=\{x_1,\mathrm{\dots },x_{\mathrm{\ell }}\}$ has $\mathrm{\ell }$-variables ordered by a total order $\prec$, w.l.o.g., $x_1\prec x_2\prec \mathrm{\dots }\prec x_{\mathrm{\ell }}$. For an index $k\in [\mathrm{\ell }]$ and a mapping $\tau :\{x_1,\mathrm{\dots },x_k\}\to [n]$, we define the set:

Intuitively, the set $⟦𝒜⟧(s,\tau )$ restricts the output set $⟦𝒜⟧(s)$ to all outputs in $⟦𝒜⟧(s)$ which coincide with $\tau$ for variables $x_i$ before the variable $x_k$, and that have a position before $\tau (x_k)$ for the variable $x_k$. If $\tau ={\mu }_{\mathrm{\varnothing }}$ is the empty mapping, we define $⟦𝒜⟧(s,\tau )=⟦𝒜⟧(s)$.

For the sake of presentation, we denote by $\mathrm{\#}⟦𝒜⟧(s)$ (resp. $\mathrm{\#}⟦𝒜⟧(s,\tau )$) the number $|⟦𝒜⟧(s)|$ (resp. $|⟦𝒜⟧(s,\tau )|$) of outputs in $⟦𝒜⟧(s)$ (resp. $⟦𝒜⟧(s,\tau )$). For direct access, we are interested in finding efficient algorithms for computing $\mathrm{\#}⟦𝒜⟧(s,\tau )$ because of the following connection.

A similar proof can be found in [17]. For the convenience of the reader and because we will use a slightly more complicated variant later, we give a quick sketch here. Let ${\mu }_i=⟦𝒜⟧(s)[i]$. The idea is to first compute ${\mu }_i(x_1)$ by observing the following: ${\mu }_i(x_1)$ is the smallest value $j_1\in [n]$ such that $\mathrm{\#}⟦𝒜⟧(s,(x_1\mapsto j_1))\ge i$. This value can be found in time $O(T\cdot \log n)$ by performing a binary search on $\{\mathrm{\#}⟦𝒜⟧(s,(x_1\mapsto j_1))\mid j_1\le n\}$. Once we have found ${\mu }_i(x_1)$, we compute ${\mu }_i(x_2)$ similarly by observing that it is the smallest value $j_2$ such that $\mathrm{\#}⟦𝒜⟧(s,(x_1\mapsto j_1,x_2\mapsto j_2))\ge i-\mathrm{\#}⟦𝒜⟧(s,(x_1\mapsto j_1-1))$. The claim then follows by a simple induction. $◀$ Given Lemma 6, in the following we concentrate our efforts on developing an index structure for efficiently computing $\mathrm{\#}⟦𝒜⟧(s,\tau )$ for every $k\in [\mathrm{\ell }]$ and every $\tau :\{x_1,\mathrm{\dots },x_k\}\to [n]$.

Let $𝒜=(Q,\mathrm{\Sigma },X,\mathrm{\Delta },q_0,F)$ be an unambiguous functional vset automaton. For any letter $a\in \mathrm{\Sigma }$, we define the matrix $M_a\in {\mathbb{N}}^{Q\times Q}$ such that for every $p,q\in Q$:

Strictly speaking, the matrix $M_a$ depends on $𝒜$ and we should write $M_a^{𝒜}$; however, $𝒜$ will always be clear from the context and, thus, we omit $𝒜$ as a superscript from $M_a$. Since $𝒜$ is functional, for every pair of states $p,q\in Q$ and $a\in \mathrm{\Sigma }$ there exists at most one transition $(p,a,S,q)\in \mathrm{\Delta }$. Then $M_a$ contains a $1$ for exactly the pairs of states that have a transition with the letter $a$. For this reason, one can construct $M_a$ in time $O({|Q|}^2)$ for every $a\in \mathrm{\Sigma }$. Figure 1(c) gives an example of matrices $M_a$ and $M_b$ for the automaton ${𝒜}_0$ from Example 2.

We can map strings to matrices in ${\mathbb{N}}^{Q\times Q}$ by homomorphically extending the mapping $a\mapsto M_a$ from letters to strings by mapping every string $s=a_1\mathrm{\dots }{a}_n$ to a matrix $M_s$ defined by the product $M_s:=M_{a_1}\cdot M_{a_2}\cdot \mathrm{\dots }\cdot M_{a_n}$. For $ϵ$, we define $M_{ϵ}=I$ where $I$ is the identity matrix in ${\mathbb{N}}^{Q\times Q}$. Note that this forms an homomorphism from strings to matrices where $M_{s_1{s}_2}=M_{s_1}\cdot M_{s_2}$ for every pair of strings $s_1,s_2\in {\mathrm{\Sigma }}^{\ast }$. It is easy to verify that for all states $p,q\in Q$ we have that $M_s[p,q]$ is the number of partial runs from $p$ to $q$ of $𝒜$ over $s$. Furthermore, if we define ${\overrightarrow{q}}_0$ as the (row) vector such that ${\overrightarrow{q}}_0[p]=1$ if $p=q_0$ and $0$, otherwise, and $\overrightarrow{F}$ as the (column) vector such that $\overrightarrow{F}[p]=1$ if $p\in F$ and $0$ otherwise, then we have the following equality between number of outputs and matrix products: $\mathrm{\#}⟦𝒜⟧(s)={\overrightarrow{q}}_0\cdot M_s\cdot \overrightarrow{F}.$

Our goal is to have a similar result for calculating $\mathrm{\#}⟦𝒜⟧(s,\tau )$ given a mapping $\tau :\{x_1,\mathrm{\dots },x_k\}\to [n]$. For this purpose, for every string $s=a_1\mathrm{\dots }{a}_n$, we define the matrix $M_s^{\tau }$ as follows. Recall that ${\tau }^{-1}$ is the set-inverse of $\tau$. Then, for every $a\in \mathrm{\Sigma }$ and $i\in [n]$, define the matrix $M_{a,i}^{\tau }\in {\mathbb{N}}^{Q\times Q}$ such that for every $p,q\in Q$:

Finally, we define $M_s^{\tau }=M_{a_1,1}^{\tau }\cdot M_{a_2,2}^{\tau }\cdot \mathrm{\dots }\cdot M_{a_n,n}^{\tau }$. Intuitively, Condition (1) for $M_{a,i}^{\tau }[p,q]=1$ makes sure that all runs of $𝒜$ over $s$ counted by $M_s^{\tau }$ must take transitions at position $i$ that contain all variables $x_j$ with $\tau (x_j)=i$ and . Note that we remove $x_k$ from ${\tau }^{-1}(i)$ since $x_k$ has a special meaning in $\tau$. Indeed, Condition (2) for $M_{a,i}^{\tau }[p,q]=1$ restricts $x_k$ such that its assignment must be before or equal to position $i$. For this second condition, we exploit the set $X_q$ of a functional vset automata, that gives us information of all variables that have been used until state $q$.

It is important to notice that if $i\notin \mathrm{𝗋𝖺𝗇𝗀𝖾}(\tau )$ then $M_{a_i,i}^{\tau }=M_{a_i}$. Since $\mathrm{𝗋𝖺𝗇𝗀𝖾}(\tau )$ has at most $k$ elements, the sequences $M_{a_1},\mathrm{\dots },M_{a_n}$ and $M_{a_1,1}^{\tau },\mathrm{\dots },M_{a_n,n}^{\tau }$ differ in at most $k$ matrices. In particular, if $\tau$ is the empty mapping, then $M_s^{\tau }=M_s$ as expected. Finally, similarly to $M_a$ one can compute $M_{a,i}^{\tau }$ in time $O({|Q|}^2)$ for any $a\in \mathrm{\Sigma }$ assuming that we have $\tau$ and ${\tau }^{-1}$.

Similarly to the relation between $\mathrm{\#}⟦𝒜⟧(s)$ and $M_s$, we can compute $\mathrm{\#}⟦𝒜⟧(s,\tau )$ by using $M_s^{\tau }$ as the following result shows.

Now that we have defined the main technical tools, we can present the algorithm for the preprocessing and direct access of an unambiguous functional vset automaton $𝒜$ over a string $s=a_1\mathrm{\dots }{a}_n$. For this purpose, we will assume here the existence of a data structure for maintaining the product of matrices ${\{M_{a_i,i}^{\tau }\}}_{i\in [n]}$ to then present and analyze the algorithms. In Section 5, we will explain this data structure in full detail.

Suppose the existence of a data structure $D$ that given values $n,m\in \mathbb{N}$ maintains $n$ square matrices $M_1,\mathrm{\dots },M_n$ of size $m\times m$. This data structure supports three methods called $\mathrm{𝗂𝗇𝗂𝗍}$, $\mathrm{𝗌𝖾𝗍}$, and $\mathrm{𝗈𝗎𝗍}$ which are defined as follows:

• $\mathrm{■}$

  $D\leftarrow \mathrm{𝗂𝗇𝗂𝗍}(M_1,\mathrm{\dots },M_n)$: receive as input the initial $n$ matrices $M_1,\mathrm{\dots },M_n$ of size $m\times m$ and initialize a data structure $D$ storing the matrices $M_1,\mathrm{\dots },M_n$;

• $\mathrm{■}$

  $D^{\prime }\leftarrow \mathrm{𝗌𝖾𝗍}(D,j,M)$: receive as input a data structure $D$, a position $j\le n$, an $m\times m$-matrix $M$, and output a data structure $D^{\prime }$ that is equivalent to $D$ but its $j$-th matrix $M_j$ is replaced by $M$; and

• $\mathrm{■}$

  $M\leftarrow \mathrm{𝗈𝗎𝗍}(D)$: receive as input a data structure $D$ storing matrices $M_1,\mathrm{\dots },M_n$ and outputs a pointer to the matrix $M:=M_1\cdot \mathrm{\dots }\cdot M_n$, i.e., the product of the $n$ matrices.

Further, we assume that method $\mathrm{𝗌𝖾𝗍}$ is persistent [22], meaning that each call to $\mathrm{𝗌𝖾𝗍}$ produces a new data structure $D^{\prime }$ without modifying the previous data structure $D$.

Assuming the existence of the data structure $D$, in Algorithm 1 we present all steps for the preprocessing and direct access of an unambiguous functional vset automaton $𝒜$ over a string $s=a_1\mathrm{\dots }{a}_n$. For the sake of presentation, we assume that $𝒜$, $s$, and the data structure $D$ are available globally by all procedures.

Algorithm 1 uses all the tools developed in this section for solving the MSO direct access problem. The preprocessing (Algorithm 1, left) receives as input the vset automaton and the string and constructs the data structure $D$ by calling the method $\mathrm{𝗂𝗇𝗂𝗍}$ with matrices $M_{a_1},\mathrm{\dots },M_{a_n}$. The direct access (Algorithm 1, right) receives any index $i$ and outputs the $i$-th mapping $\tau$ in $⟦𝒜⟧(s)$ by following the strategy of Lemma 6. Specifically, starting from an empty mapping $\tau$ (line 16), it finds the positions for variables $x_1,\mathrm{\dots },x_{\mathrm{\ell }}$ by binary search for each variable $x_k$ (line 16-17). After finding the value $j$ for $x_k$, it decreases the index $i$ by calculating the difference of outputs just before $j$ (line 19), updates $\tau$ with $(x_k\mapsto j)$ (line 20), and updates $D$ with the new value of $x_k$ (line 21). We use the auxiliary procedures CalculateDiff and UpdateStruct to simplify the presentation of these steps. The workhorse of the direct access is the procedure BinarySearch. It performs a standard binary search strategy for finding the value for variable $x$, by using the reduction of Lemma 6 to the counting problem and the matrix characterization $\mathrm{\#}⟦𝒜⟧(s,\tau )$ of Lemma 8.

The correctness of Algorithm 1 follows from Lemma 6 and 8. Regarding the running time, suppose that methods $\mathrm{𝗂𝗇𝗂𝗍}$, $\mathrm{𝗌𝖾𝗍}$, and $\mathrm{𝗈𝗎𝗍}$ of the data structure $D$ take time $t_{\mathrm{𝗂𝗇𝗂𝗍}}$, $t_{\mathrm{𝗌𝖾𝗍}}$, and $t_{\mathrm{𝗈𝗎𝗍}}$, respectively. For the preprocessing, one can check that the running time is $O({|Q|}^2\cdot |s|+t_{\mathrm{𝗂𝗇𝗂𝗍}})$ where it takes $O({|Q|}^2\cdot |s|)$ for creating the matrices $M_{a_1},\mathrm{\dots },M_{a_n}$. For the direct access, one can check that it takes time $O(|X|\cdot \log (|s|)\cdot (t_{\mathrm{𝗌𝖾𝗍}}+t_{\mathrm{𝗈𝗎𝗍}}))$ for each index $i$.

The next section shows how to implement the data structure $D$ and its methods $\mathrm{𝗂𝗇𝗂𝗍}$, $\mathrm{𝗌𝖾𝗍}$, and $\mathrm{𝗈𝗎𝗍}$. In particular, we show that the running time of these methods will be $t_{\mathrm{𝗂𝗇𝗂𝗍}}=O({|Q|}^{\omega }\cdot {|X|}^2\cdot |s|)$, $t_{\mathrm{𝗌𝖾𝗍}}=O({|Q|}^{\omega }\cdot {|X|}^2\cdot \log (|s|))$, and $t_{\mathrm{𝗈𝗎𝗍}}=O(1)$. Overall, the total running time of Algorithm 1 will be $O({|Q|}^{\omega }\cdot {|X|}^2\cdot |s|)$ for the preprocessing and $O(|Q{|}^{\omega }\cdot |X{|}^3\cdot \log {(|s|)}^2)$ for each direct access as stated in Theorem 3.