💻 computer science

Scoped MSO, Register Automata, and Expressions: Equivalence over Data Words

This paper establishes the expressive equivalence between nondeterministic register automata with guessing and two new formalisms, Scoped MSO logic and Data-Regular Expressions, thereby providing a comprehensive descriptive theory that bridges automata, logic, and expressions over data words.

Original authors: Radosław Piórkowski

Published 2026-02-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Radosław Piórkowski

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 trying to describe a very long, complex story. In the world of computer science, this story is called a "Data Word."

Think of a Data Word like a train. Each carriage has two things:

A Label (like "Passenger," "Cargo," or "Mail"). This is simple and finite (like the alphabet A, B, C).
A Ticket Number (like a unique ID, a timestamp, or a database key). This is the "Data." The problem is, there are infinite possible ticket numbers. You can't list them all.

For decades, computer scientists have struggled to find a simple way to describe patterns in these trains. The usual tools (like standard regular expressions or logic) break down when the ticket numbers get too big or too infinite.

This paper by Radosław Piórkowski is like a master key that finally unlocks the door. It proves that three very different ways of describing these data trains are actually the same thing.

Here is the breakdown of the three tools and how they connect, using simple analogies.

1. The Machine: The "Register Automaton" (The Detective)

Imagine a detective trying to solve a crime on this infinite train. The detective has a limited number of notebooks (registers).

They can pick up a ticket from a carriage and write it in a notebook.
They can look at a new ticket and ask, "Is this the same number as the one in my notebook?"
The Twist: Sometimes, the detective has to make a guess. "I bet this new ticket matches a number I haven't seen yet!"
- Weak Guessing: The detective guesses a number that actually appears somewhere else on the train later.
- Strong Guessing: The detective guesses a completely made-up number that never appears on the train.

The paper focuses on detectives who can make Weak Guesses. It turns out, for most real-world scenarios (like equality checks or ordering numbers), you don't actually need the "Strong Guessing" superpower; you can get away with just weak guesses.

2. The Logic: "Scoped MSO" (The Storyteller with a Flashlight)

Usually, logic is like a narrator who can see the whole train at once and say, "There is a ticket here that matches a ticket there." But if the narrator tries to compare every ticket to every other ticket, the story becomes impossible to read (undecidable).

Piórkowski introduces a new logic called Scoped MSO.

The Flashlight (Segment Modality): Instead of looking at the whole train, the narrator shines a flashlight on a specific segment of the train. They can only compare tickets within that lit-up segment.
The Rule: The narrator is only allowed to compare a ticket in the segment to a "top-level" ticket (one they picked up at the start of the segment). They can't get too tangled up comparing random tickets deep inside the segment.

This restriction keeps the story simple and solvable, but it's still powerful enough to describe exactly what the Detective (the Automaton) can do.

3. The Expression: "Data-Regular Expressions" (The Recipe Book)

Regular expressions are like recipes for building strings (e.g., A*B means "any number of As followed by a B").

The Problem: How do you write a recipe for infinite ticket numbers?
The Solution: The paper introduces Data-Regular Expressions (DRE).
- Instead of just saying "match A then B," the recipe says: "Match a block of A, then k-contract (overlap) with a block of B."
- The Analogy: Imagine you are building a wall with bricks. To connect two sections of the wall, you need a specific number of bricks to overlap so the structure holds. The "k-contracting" operation ensures that the "overlap" (the data values passed from one part of the expression to the next) is limited to a fixed number of bricks (registers). This mimics the detective's limited notebooks.

The Big Reveal: The Trinity

The paper proves a "Holy Trinity" of equivalence. It shows that for data words:

The Detective (Automaton) can do exactly what The Storyteller (Logic) can describe, which is exactly what The Recipe Book (Expression) can build.

Why is this a big deal?

Robustness: In the old days, moving from finite alphabets (A-Z) to infinite ones broke the rules. This paper restores the "robustness" of regular languages. It shows that even with infinite data, the concept of "regularity" is stable.
New Tools: If you have a problem that is hard to solve with a machine, you can translate it into logic or an expression, solve it there, and translate it back.
Decidability: Because the logic is restricted (Scoped), we can actually write computer programs to check if these descriptions make sense (satisfiability), which wasn't always possible before.

Summary Metaphor

Imagine you are trying to organize a massive library with infinite book titles.

The Automaton is a librarian with a small cart who can only carry a few books at a time to check for duplicates.
The Logic is a catalog system that only lets you compare books on the same shelf (segment) to avoid confusion.
The Expressions are a set of instructions for stacking books, ensuring you only overlap the top few books when moving from one shelf to another.

This paper proves that if you can organize the library with the cart, you can also do it with the catalog or the instructions. They are all different languages describing the same underlying reality.

This paper presents a comprehensive descriptive theory for Nondeterministic Register Automata with Guessing (NRAg) over infinite alphabets (data words). It establishes a "Kleene-like" trinity of equivalences, connecting automata, logic, and expressions, thereby restoring the robustness of regular language theory to the domain of data words.

1. Problem Statement

In classical language theory over finite alphabets, regular languages are equivalently characterized by Finite Automata, Regular Expressions, and Monadic Second-Order (MSO) Logic. However, this equivalence breaks down for data words (sequences over $\Sigma \times A$ , where $A$ is an infinite data domain like $\mathbb{N}$ or $\mathbb{Q}$ ).

The Gap: Existing logics for data words are either too weak to capture the full power of register automata or too strong (leading to undecidability). Specifically, standard MSO extended with data equality allows encoding Turing machines, making satisfiability undecidable.
The Challenge: NRAg are the standard baseline for data languages but lack a natural logical characterization. Furthermore, NRAg allow "guessing" (introducing fresh data values not present in the input), which complicates logical definitions that typically rely on values existing in the input structure.

2. Methodology and Key Contributions

The author introduces two new formalisms to bridge the gap: Scoped MSO (a logic) and Data-Regular Expressions (DRE).

A. Scoped MSO ($MSOS$)

The paper defines a restricted version of MSO tailored to the capabilities of register automata.

Segment Modality ( $\mathcal{X}\phi$ ): A novel operator that evaluates a formula $\phi$ on all contiguous sub-intervals (segments) defined by a set of cut-points $X$ . This allows the logic to reason about "live intervals" of register values without global quantification.
Syntactic Restrictions (Well-formedness): To prevent undecidability, the logic imposes a strict constraint on data atomic formulas $R(x)$ : they can contain at most one nested variable (a variable bound by a quantifier inside a negation or scope). This prevents arbitrary cross-position data comparisons that exceed the finite memory of a register automaton.
Scope: The logic is proven equivalent to NRAg under the condition that the data domain admits the elimination of strong guessing.

B. Data-Regular Expressions (DRE)

The paper proposes a minimalist expression calculus that mirrors the structure of classical regular expressions but adapts to data constraints.

Quantifier-Free Regions: The atomic building blocks are not single words but "regions" (sets of words sharing the same quantifier-free type).
$k$ -Contracting Concatenation ( $\cdot_k$ ): A parameterized concatenation operator. Unlike standard concatenation, $K \cdot_k L$ requires an overlap of length $k$ between the suffix of a word in $K$ and the prefix of a word in $L$ . This parameter $k$ corresponds to the number of registers, modeling the finite interface through which data values are transferred between automaton components.
$k$ -Star: An iteration operator adapted to this contracting concatenation.

C. The Equivalence Theorem

The central result is the establishment of the following equivalence for any finite alphabet $\Sigma$ and atoms $A$ (where $A$ admits elimination of strong guessing):
$\text{NRAg}[\Sigma, A] \equiv \text{DRE}[\Sigma, A] \equiv MSOS[<, \Sigma, A]$

3. Technical Results and Proofs

Elimination of Strong Guessing: The paper formalizes the condition where an NRAg with "strong guessing" (guessing values that never appear in the input) can be converted into an equivalent automaton that only performs "weak guessing" (guessing values that do appear). This property holds for standard domains like equality atoms ( $\mathbb{N}, =$ ) and dense order atoms ( $\mathbb{Q}, <$ ).
Automata to Expressions: The proof involves separating the finite control (transitions) from data consistency. The control flow is described by a classical regular expression, while data constraints are encoded into local blocks of length $2k+1$ representing register states before, during, and after a transition.
Expressions to Automata: The construction uses the $k$ -contracting concatenation to simulate the "guess and replay" mechanism. The automaton nondeterministically guesses the $k$ -length overlap (interface), stores it in registers, and replays it to verify consistency between the two concatenated parts.
Logic to Automata: The translation from $MSOS$ to NRAg involves "unfolding" the scope modality. Top-level variables are handled by auxiliary tracks carrying witness values. The logic is compiled into a locally testing formula (checking only current positions) over an expanded alphabet, which is then recognized by a 0-register automaton, finally projected back to the original alphabet.
Automata to Logic: The reverse direction uses the "live intervals" of register values. The logic guesses a run skeleton (sequence of transitions) and uses the $\mathcal{X}$ modality to recursively select witness positions for register values within their live intervals. The "alternating disjointness" of operating intervals (intervals formed by pairs of register live ranges) allows the logic to select witnesses independently without violating the well-formedness constraint.

4. Significance and Implications

Restoring Robustness: This work successfully extends the classical "Kleene Theorem" (Automata $\leftrightarrow$ Expressions $\leftrightarrow$ Logic) to the domain of data words, providing a unified theoretical framework.
Decidability: By characterizing NRAg via $MSOS$, the paper implies that the satisfiability problem for $MSOS$ is decidable if and only if the emptiness problem for NRAg is decidable. Since NRAg emptiness is decidable for standard atoms, this provides a decidable logical fragment for data words.
Tool for Open Problems: The logical formalism offers a new toolkit for tackling open problems in data language theory. For instance, it may provide insights into Colcombet's conjecture regarding the separability of disjoint NRAg languages by Unambiguous Register Automata.
Extensions: The framework is shown to extend to infinite words ( $\omega$ -words) with Büchi acceptance and can be adapted for subclasses like deterministic register automata (without guessing) by modifying the scope quantifiers.

In summary, the paper provides a rigorous descriptive theory for register automata, demonstrating that with the right syntactic restrictions (Scoped MSO) and structural operators ( $k$ -contracting concatenation), the expressive power of register automata can be fully captured by both logic and expressions, mirroring the elegance of classical regular language theory.