用两人通信模型统一刻画各类函数的正则性，突破布尔输出限制。
Regularity as seen by Alice and Bob
- 将输入分给阿丽丝和鲍勃，通过固定轮次通信计算函数值。
- 在任意输出域下，该模型与已知计算模型等价。
- 适用于无限字母表的原子语言，适合形式化理论研究者。
本文旨在提出一个统一模型，用于在不同输出域下对正则性进行类似Nerode的刻画。基于Hauser在通信复杂性中的工作，我们放宽可计算性假设并允许非布尔输出域。考虑类型为Σ^* → ℝ（Σ为有限字母表，ℝ为任意域）的函数。针对若干具体域，我们证明该模型与已有计算模型一致。我们进一步猜想：对当前缺乏Nerode型正则性刻画的其他域，该对应关系同样成立，并提供了充分支持证据。在此模型中，输入串w被划分为w₁w₂分发给两个协作方阿丽丝和鲍勃，双方交换常数轮消息以计算函数值。每条消息为输出域元素或来自有限信号集的信号，且需对所有合法划分产生正确输出。我们还将框架扩展至名义集下的无限字母表情形，研究其在带原子词的语言上的表达能力。
原文摘要 · Abstract (English)
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 $Σ^* \to \domain$, where $Σ$ 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。