Search papers, labs, and topics across Lattice.
This paper introduces a unifying model for characterizing regularity in functions with non-Boolean output domains, extending the principles of Nerode-style characterizations. By relaxing computability assumptions and employing a communication complexity framework, the authors demonstrate that their model aligns with established computation models for several domains, while also conjecturing similar correspondences for others lacking such characterizations. The findings suggest a robust framework for understanding regularity across diverse computational contexts, supported by evidence from both finite and infinite alphabets.
Regularity can be understood in a broader context, revealing connections across diverse output domains that challenge traditional assumptions in computation theory.
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^* \to \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 = w_1 w_2$ 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 = w_1 w_2$. We further extend the framework to infinite alphabets in the setting of nominal sets, and investigate its expressiveness on languages of words with atoms.
