# Regularity as seen by Alice and Bob

arXiv: https://arxiv.org/abs/2607.13782 · HTML: https://mlsanity.com/paper/2607.13782/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 58 references that are in the map.
- First posted on arXiv 15 Jul 2026.

## Abstract (arXiv)

The goal of this paper is to propose a unifying model for Nerode-style characterizations of regularity across functions with different output domains. Building on Hauser's work in communication complexity, we generalize the setting by relaxing the computability assumptions and allowing non-Boolean output domains. We consider functions of type Sigma^* → domain, where Sigma is a finite alphabet and domain is an arbitrary domain. For several domains, we show that the model coincides with known models of computation. We further conjecture that an analogous correspondence holds for other domains that currently lack a Nerode-style characterization of regularity, and we provide ample supporting evidence. In the model, an input string w is split as w = w1 w2 and distributed between two cooperating parties, Alice and Bob, who exchange a constant number of messages to compute the value of the function. Each message is either an element of the output domain or a signal drawn from a finite set of signals, and the parties must produce the correct output for every admissible split w = w1 w2. We further extend the framework to infinite alphabets in the setting of nominal sets, and investigate its expressiveness on languages of words with atoms.