Regularity Through Alice and Bob: A Unifying View of Nerode-Style Characterizations

Lead

Regular languages are usually introduced through finite automata, regular expressions, and the Myhill–Nerode theorem. But the classical story is largely Boolean: a word is either in a language or not. The arXiv paper “Regularity as seen by Alice and Bob” asks a broader question: what should regularity mean for functions whose outputs live in domains richer than true or false?

The authors approach this by importing a communication-complexity perspective. Instead of letting one machine read the whole word, they split the input w into w = w1w2. Alice receives one part, Bob receives the other, and the two cooperating parties must compute the value of the function using only a constant number of messages.

Key points

• A broader object of study: The paper considers functions of type Σ* → D, where Σ is a finite alphabet and D is an arbitrary output domain. This generalizes the usual language-recognition setting.
• Regularity as controlled communication: For every admissible split of the input, Alice and Bob must produce the correct output. The defining constraint is that only a constant number of messages may be exchanged.
• Restricted but expressive messages: Each message is either an element of the output domain or a signal from a finite set. This keeps a finite-control flavor while allowing non-Boolean outputs.
• Links to existing models: For several domains, the authors show that their communication model coincides with known models of computation, suggesting that the framework is not merely a new definition but a common abstraction.
• Beyond finite alphabets: The paper also extends the setting to infinite alphabets using nominal sets and studies expressiveness for languages of words with atoms.

Why it matters

The contribution is theoretical, but it addresses a central issue in formal language theory: how to recognize when a behavior can be captured by finite, regular structure once outputs become more complex. Nerode-style results are powerful because they translate machine recognition into structural characterizations. This paper proposes that the same spirit can be expressed through a distributed computation game between Alice and Bob.

For AI and language technologies, such theory may seem distant from product systems, but it helps clarify the foundations of symbolic processing. Modern systems often manipulate structured text, programs, names, variables, and data with binding-like behavior. In such settings, classical finite-alphabet assumptions are not always natural. The extension to nominal sets and words with atoms is therefore especially relevant to the theory of richer symbolic domains.

The paper does not claim a universal theorem for every possible output domain. Rather, it proves correspondences in several cases, formulates a broader conjectural picture, and provides supporting evidence. If later work confirms more of these correspondences, the Alice-Bob view could become a useful organizing principle for generalized regularity.

Source: arXiv