paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Verifying higher-order concurrency with data automata

用数据自动机验证高阶并发程序
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 2/10 · 该论文研究高阶并发程序的形式化验证、自动机与博弈语义,属于纯 PL/形式方法,未涉及 LLM/Agent、浮点程序分析或贝叶斯程序分析,也未体现 AI 与 PL 的交叉;仅与用户对形式化验证的背景兴趣有间接关联。引用 2 inbox
Alex Dixon, Ranko Lazic, Andrzej S. Murawski, Igor Walukiewicz
crossref: 2026-09-12

AI 速览

一句话:用分离控制与内存的 split 自动机编码 FICA,并为高阶并发找到一个验证可判定片段。

论文关注高阶并发程序的分析与验证。作者以 Finitary Idealised Concurrent Algol(FICA)为对象,结合自动机理论与博弈语义,提出一种定义在树结构无限数据字母表上的 split automata,其核心特征是控制与内存分离。他们证明每个 FICA 项都可翻译成此类自动机,从而能够观察底层博弈语义的细微性质。基于该编码,作者识别出 FICA 的一个片段:含迭代与受限同步但不含递归;与完整 FICA 不同,该片段上的多种验证问题可判定。

问题
如何自动验证高阶并发程序;完整 FICA 上的多种验证问题通常不可判定。
方法
结合自动机理论与博弈语义,定义树结构无限数据字母表上的 split automata,并证明 FICA 项可编码到其中。
评估
通过识别 FICA 中带迭代和受限同步但无递归的片段,证明该片段上的多种验证问题可判定。
原文摘要(Abstract)

Using a combination of automata-theoretic and game-semantic techniques, we propose a method for analysing higher-order concurrent programs. Our language of choice is Finitary Idealised Concurrent Algol (FICA) due to its relatively simple fully abstract game model.Our first contribution is an automata model over a tree-structured infinite data alphabet, called split automata, whose distinctive feature is the separation of control and memory. We show that every FICA term can be translated into such an automaton. Thanks to the structure of split automata, we are able to observe subtle aspects of the underlying game semantics.This enables us to identify a fragment of FICA with iteration and limited synchronisation (but without recursion), for which, in contrast to the whole FICA, a variety of verification problems turn out to be decidable.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot6246,
  title = {Verifying higher-order concurrency with data automata},
  author = {Alex Dixon and Ranko Lazic and Andrzej S. Murawski and Igor Walukiewicz},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470691}
}