💻 computer science

A finer reparameterisation theorem for MSO and FO queries on strings

This paper establishes a reparameterisation theorem demonstrating that monadic second-order and first-order queries on finite strings with polynomially bounded output sizes can be MSO-definably identified using a constant number of positions and finite data, thereby confirming that dimension minimisation holds for first-order string-to-string interpretations.

Original authors: Lê Thành Dung Nguyên, Paweł Parys

Published 2026-05-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Lê Thành D\~ung Nguyên, Paweł Parys

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 are a librarian trying to find specific pairs of books on a very long, chaotic shelf. The books are just strings of letters (like "aaabba"), and you have a set of rules (a "query") to find them.

This paper is about a clever trick to simplify how we describe these searches. Instead of trying to list every single book pair that matches your rule, the authors show you can describe the search using just a few "landmarks" on the shelf.

Here is the breakdown of their discovery using simple analogies:

1. The Problem: Too Many Matches

Imagine you have a rule: "Find every pair of books where the first is a red book (an 'a') and the second is a blue book (a 'b')."
If your shelf has 100 red books and 100 blue books, you have 10,000 possible pairs. That's a lot of data to manage.

The paper asks: Can we describe these 10,000 pairs by pointing to just a few specific spots on the shelf?

2. The Solution: The "Landmark" Trick

The authors prove that if the number of matches you find is roughly proportional to the number of red books times the number of blue books, then yes, you can do it.

They show that every single valid pair can be uniquely identified by:

Pointing to one red book.
Pointing to one blue book.
Adding a tiny bit of extra "ID card" data (which is constant and doesn't grow with the shelf size).

The Analogy:
Think of the shelf as a city. Instead of giving someone a list of every possible route from a Coffee Shop to a Bakery, you tell them: "Start at this Coffee Shop, walk to this Bakery, and follow the standard map."
The paper proves that for these types of logical rules, you never need a complex map. You just need to point to the start and the end, and the rest is predictable.

3. The Secret Weapon: "Factorization Forests"

How did they prove this? They used a mathematical tool called Factorization Forests.

The Metaphor:
Imagine you have a long string of letters. The authors build a "family tree" for this string.

The leaves of the tree are the individual letters.
The branches group letters together based on patterns.
If a section of the string repeats a pattern (like "abcabcabc"), the tree groups them together as a single "super-block."

This tree helps them see the structure of the string without getting lost in the noise. It allows them to say, "Ah, this group of letters behaves exactly like that other group."

4. The "Anchor" System

Once they have this tree, they use a system of Anchors.

Imagine a leaf (a specific letter) on the tree.
The "Anchor" is a special branch above it that acts as a reference point.
The authors prove that if you have a valid pair of letters, their "Anchors" are always close to each other in the tree (like neighbors on the same floor of a building).

Because these anchors are always close, you don't need to look at the whole string to find the pair. You just look at the neighborhood of the anchors. This is why the "extra data" needed to identify the pair is so small (it's constant, or $O(1)$ ).

5. Two Types of Rules

The paper handles two types of logical rules:

MSO (Monadic Second-Order): These are powerful rules that can look at groups of things (e.g., "Find a pair where there is a red book somewhere between them").
FO (First-Order): These are simpler rules that can only look at specific positions (e.g., "Find a pair where the book at position 5 is red").

The authors show that their "Landmark Trick" works for both types. This is a big deal because the simpler rules (FO) usually require different, more fragile proofs. They managed to unify them.

6. The "Dimension Minimization" Result

Because of this trick, they prove a "Dimension Minimization" theorem.
The Analogy:
Imagine you are trying to describe a 3D object (like a cube) using a 2D drawing. Usually, you might think you need a complex 3D model to describe it.
The paper says: "If the complexity of your object is limited in a specific way, you can flatten it into a 2D drawing without losing any information."
In computer science terms: If a function (a string-to-string transformation) grows at a certain rate, you can rewrite the code that performs it to be "simpler" (lower dimensional) without changing what it does.

7. The Limit: What They Didn't Prove

The paper also includes a "Counterexample" section. They show that their trick doesn't work for every possible scenario.
They give an example where you have red books and blue books, and you try to match them to any two books of the same color.

The Trap: Even though the math says the number of matches fits the pattern, you cannot uniquely identify the pairs using just two landmarks.
Why? Because the "neighborhood" logic breaks down. The anchors get too far apart, and the simple "point to start and end" method fails. This proves their theorem is precise and has strict boundaries.

Summary

In short, this paper is a guide for simplifying complex searches on strings. It proves that for a wide class of logical rules, you don't need to track every single result individually. Instead, you can track a few "landmarks" (like specific positions in the string) and use a "family tree" of the string's structure to reconstruct the rest. This makes the logic behind these searches much more efficient and easier to understand.

Technical Summary: A Finer Reparameterisation Theorem for MSO and FO Queries on Strings

Problem Statement
The paper addresses the structural complexity of Monadic Second-Order (MSO) and First-Order (FO) queries on finite words. Specifically, it investigates the relationship between the number of results produced by a query $\phi$ and the "size" of the input as measured by other unary queries $\eta_1, \dots, \eta_\ell$ .

The central question is: If the number of results of a $k$ -ary query $\phi$ on a word $w$ is bounded by $O(\# \eta_1(w) \times \dots \times \# \eta_\ell(w))$ , can the results of $\phi$ be effectively and uniformly reparameterized by the results of the $\eta_i$ queries? In other words, can each tuple satisfying $\phi$ be identified using a tuple of positions satisfying the $\eta_i$ queries, such that the mapping is functional and has a bounded number of preimages (i.e., each $\eta$ -tuple identifies only $O(1)$ many $\phi$ -tuples)?

Methodology
The authors employ a combination of algebraic automata theory and structural combinatorics on trees (forests). The core methodology involves:

Recognizable Queries: The paper utilizes the characterization that MSO-definable (resp. FO-definable) queries are exactly those recognized by morphisms to finite (resp. finite and aperiodic) monoids.
Factorization Forests: The proof relies heavily on Simon's Factorisation Forest Theorem. The authors define a specific notion of $\mu$ $μ$ -forests for a word $w$ $w$ relative to a morphism $\mu: \Sigma^* \to M$ $μ : Σ^{*} \to M$ . These forests decompose the word into hierarchical blocks based on the monoid values of infixes.
- For the MSO case, the forests rely on idempotence properties.
- For the FO case, the authors utilize an aperiodic version of factorization forests, ensuring the construction remains within FO-rational functions.
Graph Analysis on Forests: The authors construct a "points-to" graph where vertices are the positions satisfying the query $\phi$ $ϕ$ . An edge exists if the anchor of one position observes the anchor of another within the factorization forest.
- They analyze Strongly Connected Components (SCCs) of this graph.
- They prove that minimal SCCs correspond to non-overlapping infix blocks in the word.
Combinatorial Matching: By pumping these infix blocks, the authors derive a lower bound on the growth of $\phi$ relative to the $\eta_i$ queries. They apply Hall's Marriage Theorem to establish an injection from the set of minimal SCCs to the set of unary queries $\{\eta_1, \dots, \eta_\ell\}$ , thereby assigning each structural component of the query result to a specific unary witness.

Key Contributions and Results

Theorem 1 (Main Result): The paper proves that if $\# \phi(w) = O(\# \eta_1(w) \times \dots \times \# \eta_\ell(w))$ , there exists a formula $\psi$ (MSO if $\phi, \eta_i$ are MSO; FO if they are FO) that defines a total functional relation mapping results of $\phi$ to results of $\eta_1 \land \dots \land \eta_\ell$ . Crucially, this relation has $O(1)$ preimages per output.
- This result unifies the MSO and FO cases in a single proof scheme, utilizing the appropriate version of factorization forests for each logic.
- The MSO case extends a result by Bojańczyk (2022, 2023) regarding the trivial case where $\eta_i$ are always true.
- The FO case is novel; even the trivial case ( $\eta_i = \text{true}$ ) had not appeared in the literature previously for FO, as it requires ensuring the reparameterization formula remains in FO.
Theorem 2 (Dimension Minimisation): As a direct corollary, the paper establishes that dimension minimisation holds for FO string-to-string interpretations. Specifically, any FO interpretation defining a function $f$ with output size $O(|w|^\ell)$ can be effectively translated into an $\ell$ -dimensional FO interpretation defining the same function. This extends a known result for MSO interpretations to the FO setting.
Counterexample (Theorem 9): The paper demonstrates that the theorem cannot be naively generalized to arbitrary polynomial bounds. It constructs a counterexample showing that while the number of pairs $(a(x_1) \land b(x_2))$ is bounded by the sum of squares of unary counts, there is no MSO formula that reparameterizes these pairs using only pairs of identical letters $(a(y_1) \land a(y_2)) \lor (b(y_1) \land b(y_2))$ with bounded preimages. This highlights the necessity of the specific multiplicative structure in the hypothesis.

Significance and Claims
The paper claims to provide a "finer" reparameterisation theorem that refines previous understanding of query complexity on strings.

Unification: It provides a simultaneous proof for both MSO and FO logics, bridging a gap where the FO case was previously unaddressed.
Foundational Tool: The result serves as a foundational tool for dimension minimisation, a critical concept in the theory of string-to-string interpretations and polyregular functions.
Methodological Rigor: The proof introduces a specific adaptation of factorization forests (handling the aperiodic case for FO) and a rigorous graph-theoretic analysis of "iterable" nodes and anchors to bound the preimage size.
Limitations: The authors explicitly note that while the "trivial $\eta_i$ " case for trees has been solved using weighted automata (GLN25), their approach does not currently extend to trees, and the counterexample (Theorem 9) delineates the precise boundaries of the theorem's applicability.

The work is presented as a theoretical advancement in logic and automata theory, relying on established tools like Simon's theorem and Hall's Marriage Theorem, rather than proposing new experimental applications or future engineering implementations.