paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On sequentiality and well-bracketing in the π-calculus

π 演算中的顺序性与良括号性
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 2/10 · 该论文研究 π-calculus 中顺序性与良括号性的类型系统和标号互模拟,属于并发形式语义/过程演算理论;它与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等核心方向没有直接交叉。引用 0 inbox
Daniel Hirschkoff, Enguerrand Prebet, Davide Sangiorgi
crossref: 2026-09-12

AI 速览

一句话:用类型系统刻画顺序性与良括号性,并给出比普通互模拟更粗的标号互模拟,证明其可靠性与受限完备性。

论文以 π 演算作为编程语言模型,指出其上下文允许任意并发,因而区分能力过强,会使一些在更规范上下文下应成立的行为等价失效。作者关注两种常见规范:顺序性,即任意时刻只有一个计算线程;良括号性,即对外部服务的调用遵循栈式纪律。文章用类型系统形式化这两种规范,并分别定义相应的标号互模拟。这些关系比普通互模拟更粗。作者证明它们相对于各自的上文 barbed 等价是可靠的,并在一定技术条件下是完备的。通过在函数表示与存储等例子上的应用,展示了该技术的有效性。

问题
研究在 π 演算中,当上下文受顺序性或良括号性纪律约束时,如何得到合适且不过分苛刻的行为等价。
方法
用类型系统形式化顺序性与良括号性两种纪律,并为它们分别定义标号互模拟,研究其与上下文 barbed 等价的关系。
评估
证明这些标号互模拟对相应的上下文 barbed 等价可靠,并在一定技术条件下完备;通过函数表示与存储等例子说明其适用性。
原文摘要(Abstract)

The $\pi$-calculus is used as a model for programming languages. Its contexts exhibit arbitrary concurrency, making them very discriminating. This may prevent validating desirable behavioural equivalences in cases when more disciplined contexts are expected. In this paper we focus on two such common disciplines: sequentiality, meaning that at any time there is a single thread of computation, and well-bracketing, meaning that calls to external services obey a stack-like discipline. We formalise the disciplines by means of type systems. The main focus of the paper is on studying the consequence of the disciplines on behavioural equivalence. We define and study labelled bisimilarities for sequentiality and well-bracketing. These relations are coarser than ordinary bisimilarity. We prove that they are sound for the respective (contextual) barbed equivalence, and also complete under a certain technical condition. We show the usefulness of our techniques on a number of examples, that have mainly to do with the representation of functions and store.

链接与引用

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

BibTeX
@inproceedings{paperbot6193,
  title = {On sequentiality and well-bracketing in the π-calculus},
  author = {Daniel Hirschkoff and Enguerrand Prebet and Davide Sangiorgi},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470559}
}