AliceとBobのモデルがNerode流の正則性の特性を統一

新しい論文は、異なる出力領域を持つ関数にわたるNerode流の正則性の特性に対する統一的なモデルを提案し、通信複雑性におけるHauserの研究を一般化している。このモデルは計算可能性の仮定を緩和し、非ブール型の出力領域を許容する。そこでは入力文字列がAliceとBobという2つの当事者に分割され、関数の値を計算するために一定数のメッセージを交換する。

著者らは、いくつかの領域において、このモデルが既知の計算モデルと一致することを示し、名詞集合を用いて無限アルファベットへの枠組みの拡張を行った。

この研究は、Nerode流の正則性の特性を持たない他の領域でも同様の対応関係が成り立つという予想に対して、十分な支持証拠を提供している。