A new paper proposes a unifying model for Nerode-style characterizations of regularity across functions with different output domains, generalizing Hauser's work in communication complexity. The model relaxes computability assumptions to allow non-Boolean output domains, where an input string is split between two parties, Alice and Bob, who exchange a constant number of messages to compute the function value.
The authors show that for several domains, this model coincides with known models of computation and extend the framework to infinite alphabets using nominal sets.
The work provides ample supporting evidence for the conjecture that an analogous correspondence holds for other domains lacking a Nerode-style characterization of regularity.