Dynamic direct access of MSO query evaluation over strings

Pierre Bourhis, Florent Capelli, Stefan Mengel and Cristian Riveros

CRIL, Université d’Artois

ICDT 2025

March 2025

Variable Set Automata

Tagging positions in words

Automaton with variables tagging positions:

w

Positions

Run 1

x

y

Run 2

x

y

Run 3

x

y

$\llbracket A \rrbracket(w)$	$x$	$y$
(run 1)	2	4
	3	4
(run 2)	5	8
	6	8
	7	8
(run 3)	9	10

Gist of the paper: given $w$ , build a data structure allowing to access each tuple in $\llbracket A \rrbracket(w)$ efficiently.

Properties of vset automaton

Determinism¹: two edges going out of state $q$ have distinct labels.

Functionality: every path from $q_0$ to a final state tags each variable exactly once.

For each state $q$ of a functional automaton, there is a set of variables $X_q$ that are tagged before reaching $q$ .

¹: We actually do not need full determinism but only unambiguity: each tuple of $\llbracket A \rrbracket(w)$ has exactly one corresponding run.

Normalization

Let $A$ be an vset automaton. One can construct a deterministic function vset automaton $A'$ such that $\llbracket A \rrbracket = \llbracket A' \rrbracket$ .

Intuition: automata over states $2^{Q \cup X}$ .
$A'$ may be of size $exp(A)$

In this talk: $A$ is considered constant, hence assumed to be deterministic and functional.

Direct Access for vset automata

Direct access queries

Fix a (deterministic functional) automaton $A(x_1,\dots,x_k)$ (considered constant).

A direct access query for a word $w \in \Sigma^*$ :

input integer $k$ ,
output the $k$ th tuple of $\llbracket A \rrbracket(w)$ or,
fails if $k > \#\llbracket A \rrbracket(w)$ .

where $\llbracket A \rrbracket(w)$ is ordered by lexicographical ordering on $[n]^X$ .

$\llbracket A \rrbracket[3]$

$\llbracket A \rrbracket[10]$

$\llbracket A \rrbracket[5]$

$\llbracket A \rrbracket(w)$	$x$	$y$
	2	4
	3	4
	5	8
	6	8
	7	8
	9	10

Direct access complexity

Given $w \in \Sigma^*$ of length $n$ :

Precomputation phase: construct a data structure $D_w$ in time $p(n)$ .
Access phase: given $k$ , output $\llbracket A \rrbracket(w)[k]$ in time $a(n)$ using $D_w$ .

Naive approach:

$D_w$ is a materialization of $\llbracket A \rrbracket(w)$ in an array. At least $O(\#\llbracket A \rrbracket(w))$
Access phase: read the $k$ th entry of $D_w$ . $O(1)$

Can we have better preprocessing without hurting access time too much?

Contribution

We show that we can solve direct access with:

Linear time precomputation $O(n)$ ,
Polylogarithmic access time $O(\log^2(n))$ .

$O(\cdot)$ notation hides constants depending on $|A|$ but they are all polynomially bounded if $A$ is deterministic and unambiguous.

Data structure idea

Counting reduction

Let $\tau = \llbracket A \rrbracket(w)[k]$ .

$\tau(x_1)$ is the first position $p_1$ for which $\#\llbracket A \rrbracket_{x_1 \leq p_1}(w) \geq k$

	$x_1$	…	$x_k$
	$< p_1$	…	…
	$p_1$	…	…
	…	…	…
$k$	$p_1$	…	…
	…	…	…
	$p_1$	…	…
	$> p_1$	…	…

Binary search to find $p_1$ : $O(\log n)$ calls to computing $\#\llbracket A \rrbracket_{x_1 \leq p}(w) \geq k$ by changing $p$
We proceed recursively to find $\tau(x_2)$ : first value $p$ such that

$\#\llbracket A \rrbracket_{x_1 = p_1, x_2 \leq p}(w) \geq k$ $-\#\llbracket A \rrbracket_{x_1 < p_1}(w)$

Transition matrices

$M_a[q,q'] = 1$ if and only if there is a transition from $q$ to $q'$ labeled by $a$ .

$(M_{a_1} \cdot \dots \cdot M_{a_n})[q,q'] =$ number of paths from $q$ to $q'$ reading $w = a_1 \dots a_n$ .

$\sum_{q_f \in F} (M_{a_1} \cdot \dots \cdot M_{a_n})[q_0,q_f] = \#\llbracket A \rrbracket(w)$

$M_a^{x}[q,q'] = 1$ if and only if there is a transition from $q$ to $q'$ labeled by $a$ and $x$ has been tagged before $q'$ (which only depends on $q'$ by functionality).

$\sum_{q_f \in F} (M_{a_1} \cdot \dots \cdot M_{a_p}^x \cdot \dots \cdot M_{a_n})[q_0,q_f] = \#\llbracket A \rrbracket_{x \leq p}(w)$

Maintaining products

To find $\tau(x_1)$ We need to find the smallest $p$ such that:

$\#\llbracket A \rrbracket_{x_1 \leq p}(w) \geq k$

Binary search by computing the product:

$\sum_{q_f \in F} (M_{a_1} \cdot \dots \cdot M_{a_p}^x \cdot \dots \cdot M_{a_n})[q_0,q_f] = \#\llbracket A \rrbracket_{x \leq p}(w)$

Recomputing this product is too costly: $O(n)$ matrix multiplications each time.
$M_{a_1} \cdot \dots \cdot M_{a_p}^x \cdot \dots \cdot M_{a_n}$ and $M_{a_1} \cdot \dots \cdot M_{a_{p'}}^x \cdot \dots \cdot M_{a_n}$ are almost the same.
If $P_i := M_{a_1} \cdot \dots \cdot M_{a_i}$ and $Q_j := M_{a_j} \cdot \dots \cdot M_{a_n}$ have been precomputed for every $i,j$ :

$M_{a_1} \cdot \dots \cdot M_{a_p}^x \cdot \dots \cdot M_{a_n} = P_{p-1} \cdot M_{a_p}^x \cdot Q_{p+1}$

Each product in the binary search can be computed with two products.

Final data structure

Data structure $D$ to represent a product $A_1 \cdot \dots \cdot A_r$ in a semigroup such that one can quickly update $D$ so that it represents the product where $A_i$ is replaced by $B_i$ .

Dynamic word problem.

Dynamic words

Updates

In this setting, one can “update” word $w$ , e.g., insert a letter at the end.

Can we use the data structure for $w$ to construct a data structure for ${w \cdot a}$ more efficiently than rerunning $O(n)$ -precomputation?

We can update the word in $O(\log n)$ .

Cut and paste update

Given data structures $D_1$ for $w_1$ and $D_2$ for $w_2$ , $k \leq |w_1|, i,j \leq |w_2|$ :

$w_1 = a_1 \dots a_n$ , $w_2 = b_1 \dots b_n$

We can construct $D_1'$ for $w_1'$ and $D_2'$ for $w_2'$ where

$w_1' =$ $a_1 \dots a_k$ $b_i \dots b_j$ $a_{k+1} \dots a_n$

$w_2' =$ $b_1 \dots b_{j-1} b_{j+1} \dots b_m$

in time $O(\log (n+m))$ .

Cut and paste application

Cut and paste covers:

Concatenation of words (cut $w_2$ completely and paste at the end of $w_1$ )
Insertion of letter (create data structure for $w_2 = a$ in $O(1)$ , cut it and paste it in $w_1$ )
Remove substring (cut the substring)
Update letter (cut the letter and insert a new one in its place)

And so on!

Data structure idea

Maintain matrix product in a balanced tree
Use AVL tree operations to keep it balanced

Future work

Implementations:
- reasonable data structures
- updates may be cheap enough to maintain a query on a code base.
Generalizations:
- Orders that are not lexicographical
- MSO over trees.

Dynamic direct access of MSO query evaluation over strings

Variable Set Automata

Tagging positions in words

Related formalisms

Properties of vset automaton

Normalization

Direct Access for vset automata

Direct access queries

Direct access complexity

Contribution

Data structure idea

Counting reduction

Transition matrices

Maintaining products

Final data structure

Dynamic words

Updates

Cut and paste update

Cut and paste application

Data structure idea

Future work