💻 computer science

Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings

This paper presents a dynamic algorithm that enables logarithmic-time, ranked direct access to the answers of Monadic Second-Order (MSO) queries over both uncompressed and Straight-Line Program (SLP)-compressed strings, while supporting efficient updates to the compressed representation.

Original authors: Martín Muñoz

Published 2026-03-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Martín Muñoz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, ancient library (a database) containing a single, incredibly long book (a string of text). This book is so long that if you tried to write it out on paper, it would stretch from the Earth to the Moon and back a thousand times.

However, this library has a magical librarian who doesn't store the book page-by-page. Instead, the librarian stores a recipe book (called an SLP or Straight-Line Program). This recipe book is tiny. It says things like:

"Take the phrase 'Hello World'."
"Copy it twice to make 'Hello WorldHello World'."
"Take that result and paste it 1,000 times."

Even though the final book is massive, the recipe book is small and easy to carry.

The Problem: Finding a Specific Page

Now, imagine you are a detective trying to find specific clues in this giant book. You have a list of rules (an MSO Query) that say: "Find every time the word 'cat' appears right after the word 'dog', and tell me the exact page numbers."

In a normal library, you'd have to read the whole book to find these clues. But here, the book is too big to read. You need a way to jump straight to the 500th clue without reading the first 499.

This is called Direct Access. You want to say, "Give me the 500th answer," and get it instantly.

The Challenge: The "Rank" Problem

The clues aren't just random; they have an order. Maybe you want the clues sorted by where they appear in the book.

The old way: To find the 500th clue, the computer had to do a lot of heavy math, taking a long time (like searching through a maze).
The new way (This Paper): The author, Martín Muñoz, built a super-smart index.

The Solution: The "Magic Map"

The author created a special data structure (a map) that acts like a GPS for the clues.

The Pre-Work (Preprocessing): Before you ask for any clues, the librarian spends a little time building this GPS map. This takes time proportional to the size of the recipe book (the small one), not the giant book.
The Magic Trick (Binary Search): When you ask for the 500th clue, the GPS doesn't walk through the book. Instead, it plays a game of "Higher or Lower."
- It asks: "Is the 500th clue in the first half of the book?"
- It calculates the answer instantly using the recipe.
- If yes, it zooms into the first half. If no, it zooms into the second half.
- It keeps zooming in, cutting the search space in half every time, until it finds the exact spot.

The Result: Instead of taking a long time (logarithmic squared), it now takes a very short time (just logarithmic). It's like finding a needle in a haystack by using a metal detector that beeps instantly, rather than digging with a spoon.

The Twist: Editing the Book

What if you want to change the book?

"Delete the middle chapter."
"Insert a new paragraph."
"Swap two sentences."

In the past, if you changed the recipe, the whole GPS map would break, and you'd have to rebuild it from scratch.

The Paper's Innovation:
The author adapted a framework that allows the GPS to update itself instantly.

Imagine the recipe book is a set of LEGO instructions. If you change one instruction (e.g., "use red bricks instead of blue"), the author's system knows exactly which parts of the final tower change and updates the map for just those parts.
This happens almost instantly (in logarithmic time), so you can edit the book and still ask for the 500th clue immediately.

The "Compressed" Superpower

The coolest part is that this works even when the book is stored as a recipe (SLP).

Usually, computers hate working with recipes because they have to "unroll" the recipe to see the actual text, which is slow.
This new algorithm is smart enough to do the math directly on the recipe. It figures out where the 500th clue is by looking at the instructions, without ever needing to write out the full, massive book.

Summary Analogy

Think of the MSO Query as a treasure hunt.

The String is the island where the treasure is buried.
The SLP is a folded map that describes the island in a tiny square of paper.
The Old Method: To find the 500th treasure, you had to unfold the whole map, walk the whole island, and count the treasures.
The New Method: You have a magic compass. You point it at the folded map, and it instantly tells you exactly where to dig for the 500th treasure. If someone changes the island's terrain (edits the map), the compass recalibrates instantly, and you can still find the treasure without walking the whole island again.

Why does this matter?
This makes databases faster, smarter, and capable of handling massive amounts of text (like all of Wikipedia or the entire internet) without needing supercomputers. It allows us to ask complex questions and get ranked answers instantly, even if the data is constantly changing.

1. Problem Statement

The paper addresses the problem of dynamic direct (ranked) access for Monadic Second-Order (MSO) queries over strings.

The Task: Given an MSO formula $\phi(x_1, \dots, x_k)$ and a string $w$ , the system must compute the set of valid assignments (mappings) $\mu$ such that $w \models \phi(\mu)$ . The goal is not to enumerate all answers, but to retrieve the $t$ -th answer in lexicographical order (ranked access) in logarithmic time.
The Dynamic Aspect: The data structure must support edits to the string (or the compressed representation) after the initial preprocessing, allowing for efficient updates to the access structure.
The Compression Aspect: The input string $w$ may be extremely large but is provided in a compressed format known as a Straight-Line Program (SLP). An SLP is a context-free grammar generating a single string (a singleton language), allowing for exponential compression.
The Gap: Previous work (Bourhis et al., ICDT 2025) achieved direct access for MSO on uncompressed strings with $O(\log^2 |w|)$ access time. This paper aims to improve the access time to $O(\log |w|)$ and extend the result to SLP-compressed strings while maintaining dynamic update capabilities.

2. Methodology

The authors propose a framework based on Vset Automata (a variant of finite automata that tracks variable assignments) and Matrix Multiplication over a tree-like data structure.

A. Core Abstraction: Vset Automata

The MSO formula is converted into an unambiguous, functional Vset automaton $A$ . The set of answers $JAK(w)$ corresponds to the set of valid accepting runs of $A$ over $w$ . The problem is reduced to finding the $t$ -th valid run.

B. The Data Structure: Matrix Trees

The core innovation is a collection of binary trees (for uncompressed strings) or DAGs (for SLPs) where each node stores a transition matrix.

Matrix Definition: For a range of the string $[l, r]$ and a set of variables $Y \subseteq X$ , a matrix $M \in \mathbb{N}^{Q \times Q}$ is stored. The entry $M(p, q)$ counts the number of partial runs from state $p$ to state $q$ over the substring $w[l, r]$ that respect specific variable constraints (e.g., variables in $Y$ are "active" or "assigned" within this range).
Composition: These matrices allow the counting of runs over concatenated substrings via matrix multiplication: $M_{[l, r]} = M_{[l, m]} \times M_{[m+1, r]}$ .
Preprocessing:
- Uncompressed Strings: A set of $k+1$ binary trees is built (where $k$ is the number of variables). Each tree corresponds to a "slice" of variables, effectively filtering out variables assigned in previous steps.
- SLPs: The trees are replaced by structures mirroring the SLP's DAG. The matrices are computed bottom-up on the SLP grammar rules.

C. The Access Algorithm (Binary Search)

To find the $t$ -th answer, the algorithm determines the value of each variable $x_i$ sequentially ( $x_1, \dots, x_k$ ):

Binary Search: For the current variable $x_i$ , the algorithm performs a binary search over the string positions $[1, |w|]$ .
Counting: At each step of the binary search (checking a midpoint $m$ ), it calculates how many valid assignments exist where $x_i$ is mapped to a position $\le m$ . This is done by composing the relevant matrices from the data structure (cached prefix and suffix matrices).
Selection: If the count is $\ge t$ , the search moves to the left half; otherwise, it moves to the right, adjusting $t$ by subtracting the count of the left half.
Update: Once $x_i$ is fixed to a specific position $s_i$ , the data structure is updated to reflect this constraint for the subsequent variables.

D. Dynamic Updates (Editing)

To handle edits (insertions, deletions, concatenations) defined by Complex String Editing (CSE) expressions:

The authors adapt a framework by Schmid and Schweikardt (PODS 2022).
Path Duplication: When an edit affects a specific position in the string, the algorithm identifies the path of non-terminals in the SLP leading to that position. It duplicates these non-terminals to create a "fresh" path, ensuring the edit does not corrupt the shared structure of the rest of the string.
Re-computation: The matrices along this new path are recomputed and propagated upwards. This allows the data structure to reflect the edit in logarithmic time relative to the string length.

3. Key Contributions

Logarithmic Access Time: The paper reduces the direct access time for MSO queries on strings from $O(\log^2 |w|)$ to $O(\log |w|)$ (specifically $O(|Q|^\omega \cdot |X|^2 \cdot \log |w|)$ ), improving upon the state-of-the-art by a logarithmic factor.
Extension to SLPs: It is the first work to achieve direct ranked access for MSO queries over SLP-compressed strings. The preprocessing time is linear in the size of the SLP ( $O(|S|)$ ), and access remains logarithmic in the uncompressed string length ( $O(\log |w|)$ ).
Dynamic Editing: The framework supports complex edits (concatenation, extraction, insertion, deletion) on the SLP representation. The update time is logarithmic in the size of the resulting string, maintaining the efficiency of the access phase.
Generalized Framework: The solution unifies the handling of uncompressed strings and compressed SLPs under a single matrix-based logic, differing only in the underlying tree/DAG structure.

4. Results and Complexity

Let $|Q|$ be the number of states in the automaton, $|X|$ the number of variables, $|w|$ the length of the string, and $|S|$ the size of the SLP. Let $\omega$ be the matrix multiplication exponent.

Scenario	Preprocessing Time	Access Time	Update Time
Uncompressed String	$O(\|Q\|^\omega \cdot \|X\| \cdot \|w\|)$	$O(\|Q\|^\omega \cdot \|X\|^2 \cdot \log \|w\|)$	$O(\log \|w\|)$ (implied via structure)
SLP-Compressed	$O(\|Q\|^\omega \cdot \|X\| \cdot \|S\|)$	$O(\|Q\|^\omega \cdot \|X\|^2 \cdot \log \|w\|)$	$O(\log \|w\|)$

Note: The update complexity assumes the SLP is strongly balanced (depth $O(\log |w|)$ ), which can be achieved via a linear-time transformation.

5. Significance

Efficiency: The improvement from $O(\log^2)$ to $O(\log)$ access is significant for large-scale database queries where the number of answers is massive.
Scalability: By supporting SLPs, the algorithm can handle strings that are exponentially larger than the input memory footprint, making it applicable to compressed data scenarios (e.g., DNA sequences, compressed logs, XML).
Dynamic Capabilities: Unlike many static MSO evaluation techniques, this work supports dynamic data modification, which is crucial for real-time database applications.
Theoretical Foundation: It bridges the gap between formal language theory (MSO, Automata), data compression (SLPs), and database theory (direct access, ranking), providing a robust theoretical basis for querying compressed data.

6. Limitations and Future Work

Balanced SLPs: The dynamic update mechanism currently requires the SLP to be strongly balanced. While this can be enforced, it may increase the SLP size by a logarithmic factor. The authors leave open the question of whether weaker balancing criteria suffice.
Semigroups: The current approach does not generalize to MSO queries over arbitrary semigroups, a limitation noted compared to previous work.
Trees: Extending this dynamic direct access framework to trees (MSO over tree structures) is identified as a major future challenge, primarily because the "contiguity" property of strings (crucial for the matrix slicing) does not hold for trees.