💬 NLP

Regularity as seen by Alice and Bob

This paper proposes a unifying communication complexity model involving two cooperating parties, Alice and Bob, to characterize the regularity of functions with arbitrary output domains and infinite alphabets, generalizing existing results and conjecturing broader applicability.

Original authors: Omid Yaghoubi, Mikołaj Bojańczyk, Aliaume Lopez, Rafał Stefański

Published 2026-07-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Omid Yaghoubi, Mikołaj Bojańczyk, Aliaume Lopez, Rafał Stefański

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 figure out if a long, complicated story follows a simple, predictable pattern. In the world of computer science, this is the study of "regularity." Think of it like trying to spot a rhythm in a song. If you can predict the next note just by knowing the last few, the song has a rhythm. If the song is chaotic and requires you to remember the entire history of every note ever played to guess the next one, it's irregular. For decades, scientists have had a perfect way to spot this rhythm when the story is just a list of "yes" or "no" answers (like a light switch being on or off). They call this the "Myhill-Nerode Theorem," and it's the gold standard for knowing if a pattern is simple enough to be handled by a basic machine.

But what happens when the story isn't just "yes" or "no"? What if the story ends with a number, a whole new sentence, or a complex graph? The old rules get fuzzy. Some scientists say, "Oh, if it uses a little bit of math, it's regular." Others say, "No, it has to use this specific kind of math." It's like a group of musicians arguing over whether a song is "jazz" because it has a saxophone, or because it has a specific drum beat. There are dozens of definitions, and no one agrees on which one is the true definition of a "regular" pattern for these complex outputs. This confusion makes it hard to build reliable software that handles numbers, strings, or data with infinite possibilities.

This paper, titled "Regularity as seen by Alice and Bob," tries to settle the argument by introducing a new, unifying way to look at these patterns. The authors, Mikołaj Bojańczyk and his team, propose a game played by two cooperating friends, Alice and Bob. Imagine Alice has the first half of a secret code, and Bob has the second half. They can't see each other's pieces, but they need to figure out the final answer together. The rule is strict: they can only whisper a tiny, fixed number of messages to each other, no matter how long the code is. If they can solve the puzzle with just a few whispers, the pattern is "regular." If they need to shout the whole story back and forth, it's not.

The paper's main finding is that this "Alice and Bob" game acts as a universal translator for regularity. When the answer is just "yes" or "no," the game perfectly matches the old, trusted rules. But the magic happens when the answers are more complex. The authors prove that if the answer is a number (like a rational number), the game is exactly the same as a machine called a "weighted automaton," which uses simple addition and multiplication. This is a big deal because it suggests that even though these machines look different, they are actually doing the same thing.

However, the paper also draws a hard line in the sand. The authors explicitly argue against the idea that you can just add any math operation to the game. For instance, they show that if you allow Alice and Bob to use division, the game breaks down and becomes too powerful, allowing them to solve problems that shouldn't be considered "regular." They also rule out the idea that a single round of chatting is always enough; for some complex inputs (like infinite alphabets), Alice and Bob must take turns talking back and forth multiple times to get the right answer.

For string-to-string functions (turning one sentence into another), the authors don't claim to have a final, proven answer yet. Instead, they suggest a strong hypothesis: the "regular" string functions are exactly the ones Alice and Bob can compute with their limited whispers. They provide a mountain of evidence for this guess, showing that these functions behave in very specific, "well-behaved" ways—like always producing an output that isn't too huge and can be calculated quickly. They even prove this guess is true for a special case where the output is just a single letter repeated many times.

Finally, the paper tackles the tricky case of infinite alphabets, where the input isn't a fixed list of letters but an endless stream of unique symbols (like names or IDs). Here, the authors suggest that the "regular" patterns are those recognized by "unambiguous automata"—machines that never get confused about which path to take. They prove that Alice and Bob can simulate these machines, but they also show that the reverse is much harder to prove, leaving it as an open question for future researchers.

In short, this paper doesn't just offer a new definition; it offers a new lens. By viewing regularity through the eyes of two friends passing notes, the authors provide a consistent way to judge whether a complex function is simple enough to be considered "regular." While some parts are proven facts and others are well-supported guesses, the approach successfully unifies many different areas of computer science under one playful, yet rigorous, framework.

Technical Summary: Regularity as seen by Alice and Bob

1. Problem Statement

The paper addresses the lack of a unified, principled characterization of "regularity" for functions with output domains beyond the Boolean case. While regular languages (functions $f: \Sigma^* \to \{true, false\}$ ) are well-understood through equivalent models like finite automata, regular expressions, and the Myhill-Nerode theorem, the situation is fragmented for other domains:

String-to-String Functions: Multiple non-equivalent classes exist (rational, regular, polyregular), with no consensus on which constitutes "the" regular functions.
String-to-Number Functions: Distinct models like weighted automata (linear updates) and polynomial automata (polynomial updates) exist, with unclear relationships regarding which captures the correct notion of regularity.
Infinite Alphabets: For languages over infinite alphabets (where letters are only comparable for equality), lifting finite automata models results in seventeen pairwise non-equivalent models, lacking a unifying principle.

The core problem is to find a single, machine-independent framework that characterizes regularity across these diverse output domains and input settings.

2. Methodology: The Protocol Model

The authors propose a unifying model based on communication complexity, specifically adapting the work of Hauser [Hau89]. The model involves two cooperating parties, Alice and Bob, who compute a function $f: \Sigma^* \to D$ where $D$ is an arbitrary output domain.

Key Mechanisms:

Input Splitting: The input string $w$ is split arbitrarily into $w = w_1w_2$ . Alice holds $w_1$ , and Bob holds $w_2$ .
Constant Communication: The parties exchange a constant number of messages (independent of the input length).
Message Types: Messages consist of:
1. Signals: Elements from a finite set (bits or finite symbols).
2. Domain Elements: Elements from the output domain $D$ .
Black Box Restriction: Crucially, messages containing elements of $D$ cannot be "read" or inspected directly. They can only be manipulated using the predefined operations of the domain (e.g., addition and multiplication for fields, concatenation for strings). This prevents encoding the entire input string into a single domain element.
Split Invariance: The protocol must produce the same output for any split $w = w_1w_2$ of the same input string $w$ .
Non-Uniformity: Alice and Bob have unbounded computational power; the restriction lies solely in the communication bandwidth and the black box discipline.

The paper formalizes this as a protocol and investigates its expressive power for different domains $D$ .

3. Key Contributions and Results

3.1 Boolean Outputs ( $D = \{true, false\}$ )

The paper re-establishes a known result (originally by Hauser [Hau89]) to serve as a baseline:

Theorem 1.1: A language is computed by a protocol if and only if it is regular.
Significance: This confirms the model captures standard regularity and provides a foundation for generalization. The proof relies on reducing multi-round protocols to one-round protocols and applying the Myhill-Nerode theorem.

3.2 Field Outputs ( $D$ is a Field)

This is a primary contribution of the paper.

Theorem 1.2: A function $f: \Sigma^* \to D$ (where $D$ is a field) is computed by a protocol if and only if it is computed by a weighted automaton over $D$ .
Methodology: The proof reduces general protocols to scalar product protocols (where Alice and Bob compute vectors $\sigma_A(w_1)$ and $\sigma_B(w_2)$ , and the output is their dot product). It then invokes the Fliess Theorem [Fli74], which characterizes weighted automata via the finite rank of the Hankel matrix.
Insight: The split invariance constraint enforces linearity. Even though the protocol allows polynomial operations (via composition), the requirement for split invariance restricts the expressiveness to linear maps, excluding general polynomial automata.
Limitations: The equivalence holds for fields. For general semirings (e.g., free idempotent semirings), protocols may be strictly more powerful than weighted automata (e.g., they can compute string reversal, which is not a rational relation in that semiring).

3.3 String Outputs ( $D = \Gamma^*$ )

The paper investigates string-to-string functions, where the domain operation is concatenation.

Conjecture 1.3: A string-to-string function is computed by a protocol if and only if it is computed by a deterministic two-way automaton with output (the traditional definition of regular functions).
Evidence Provided:
- Implication ( $\Leftarrow$ ): Proven. Deterministic two-way automata can be simulated by protocols using crossing sequences.
- Implication ( $\Rightarrow$ ): Not fully proven, but supported by strong evidence:
  - Protocols produce outputs of linear size and are computable in linear time.
  - Protocols preserve regularity under inverse images (Boolean continuity).
  - Field Continuity: Protocols are closed under precomposition with weighted automata over fields.
  - Unary Case: The conjecture is proven for unary output alphabets, where rational functions coincide with regular functions.
Significance: If true, this provides a machine-independent characterization of regular string-to-string functions, distinguishing them from the weaker rational functions and stronger polyregular functions.

3.4 Infinite Input Alphabets

The paper extends the model to infinite alphabets (atoms) where letters are only comparable for equality, using the framework of nominal sets and orbit-finite sets.

Conjecture 6.5: A language over an infinite alphabet is computed by an orbit-finite protocol if and only if it is recognized by an unambiguous register automaton.
Context: Deterministic register automata are too weak (cannot handle certain reversals), and nondeterministic ones are too strong (can detect repetitions that protocols cannot). Unambiguous automata (at most one accepting run) are proposed as the "Goldilocks" model.
Results:
- Implication ( $\Leftarrow$ ): Proven. The authors construct a multi-round protocol that simulates an unambiguous automaton by iteratively narrowing down the set of possible intermediate states using orbits and a variant of the sunflower lemma.
- Implication ( $\Rightarrow$ ): Evidence provided via weighted orbit-finite automata. The authors prove an Orbit-Finite Fliess Theorem (Theorem 6.19), showing that protocols compute functions with orbit-finitely spanned left derivatives. This implies protocols are decidable and lie within the intersection of weighted and nondeterministic models.
Novelty: Unlike the finite alphabet case, protocols for infinite alphabets cannot be reduced to one round; the interactive nature is essential.

4. Significance and Claims

The paper claims to provide a unifying model for regularity that transcends specific automata definitions. Its significance lies in:

Machine Independence: It characterizes regularity via communication constraints (constant messages, black box operations) rather than specific state-transition structures.
Unification: It suggests that diverse models (weighted automata, deterministic two-way transducers, unambiguous register automata) are all instances of the same underlying principle: constant information flow with restricted domain operations.
New Characterizations: It offers machine-independent characterizations for weighted automata (Theorem 1.2) and proposes one for regular string-to-string functions (Conjecture 1.3) and unambiguous register automata (Conjecture 6.5).
Computational Properties: The model naturally enforces desirable properties like linear output size and computability, which are not always guaranteed in other transducer models (e.g., polyregular functions).

The authors remain modest regarding the string-to-string and infinite alphabet cases, presenting them as conjectures supported by substantial evidence (proofs of one direction, unary cases, and structural properties) rather than fully resolved theorems. They explicitly avoid claiming results for general semirings or arbitrary output domains where the "black box" restriction might not yield well-behaved functions.

Technical Summary: Regularity as seen by Alice and Bob

1. Problem Statement

2. Methodology: The Protocol Model

3. Key Contributions and Results

3.1 Boolean Outputs (D={true,false}D = \{true, false\}D={true,false})

3.2 Field Outputs (DDD is a Field)

3.3 String Outputs (D=Γ∗D = \Gamma^*D=Γ∗)

3.4 Infinite Input Alphabets

4. Significance and Claims

More like this

3.1 Boolean Outputs ( $D = \{true, false\}$ )

3.2 Field Outputs ( $D$ is a Field)

3.3 String Outputs ( $D = \Gamma^*$ )