paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Distributed Asynchronous Games With Causal Memory are Undecidable

具有因果记忆的分布式异步博弈是不可判定的
LMCS vol.Volume 18, Issue 32022匹配度 1/10 · 该论文研究异步自动机与因果记忆下的分布式控制不可判定性，属于并发/自动机理论，与用户核心研究方向（LLM/Agent 结合静态分析、浮点程序分析、贝叶斯程序分析）没有直接交集。引用 6 inbox
Hugo Gimbert
逻辑与自动机并发、并行与内存模型
crossref: 2026-09-10

AI 速览

一句话：证明异步自动机与因果记忆控制器的分布式控制问题不可判定。

论文研究分布式控制问题：被控对象为异步自动机，多个控制器使用因果记忆，控制目标是将每个进程置于各自的局部接受状态。作者证明，在该设定下分布式控制问题是不可判定的。这一结果给出了异步分布式博弈在因果记忆语义下的可判定性边界，表明即使目标仅要求各进程达到局部接受状态，也不存在一般性判定算法。该不可判定性对分布式系统控制与异步自动机博弈的分析具有理论意义。

问题
在异步自动机作为被控对象、控制器使用因果记忆、目标为各进程进入局部接受状态的设定下，分布式控制问题是否可判定。
方法
论文通过理论证明给出该分布式控制问题的不可判定性结果。
评估
以不可判定性证明作为主要评估，表明不存在判定该问题的算法。
原文摘要（Abstract）

We show the undecidability of the distributed control problem when the plant is an asynchronous automaton, the controllers use causal memory and the goal of the controllers is to put each process in a local accepting state.

链接与引用

DOI 原文 · PDF（开放获取） ·

BibTeX 
@article{paperbot1656,
  title = {Distributed Asynchronous Games With Causal Memory are Undecidable},
  author = {Hugo Gimbert},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 18, Issue 3},
  year = {2022},
  doi = {10.46298/lmcs-18(3:30)2022}
}