paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Domains and event structures for fusions

面向融合的域与事件结构
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 1/10 · 论文属于并发理论与形式语义,研究 event structures 与 domain 对偶及非线性图重写语义,与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析无直接交集;仅在 PL/形式方法大领域上勉强相关。引用 9 inbox
Paolo Baldan, Andrea Corradini, Fabio Gadducci
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出 connected event structures 及其对偶域,刻画非线性图重写等融合计算的并发语义。

稳定事件结构与素代数域的对偶是并发理论基石,用 configuration 偏序刻画因果性,并支撑 Petri 网、线性图重写等并发语义。但稳定性对某些形式系统过严:非线性图重写等计算步会合并状态部分(fusion),如带名字传递演算的图形编码。本文定义一类自然推广素代数域的域,用于建模带 fusion 的形式系统语义;并通过范畴等价的对偶结果,识别出对应的事件结构,称为 connected event structures。作者证明 connected event structures 恰为非线性图重写系统产生的事件结构。此外,一般 unstable event structures 的范畴余反射到该域范畴,从而刻画此类事件结构的 configuration 偏序。

问题
经典 stable event structures 与 prime algebraic domains 的对偶依赖稳定性,难以刻画非线性图重写等会合并状态部分的融合型计算。
方法
通过范畴论对偶,定义素代数域的自然推广,并引入 connected event structures,证明其与相应域范畴等价。
评估
以范畴等价和余反射等数学证明为主要评估,证明 connected event structures 恰为非线性图重写系统的语义,并刻画一般 unstable event structures 的 configuration 偏序。
原文摘要(Abstract)

Stable event structures, and their duality with prime algebraic domains (arising as partial orders of configurations), are a landmark of concurrency theory, providing a clear characterisation of causality in computations. They have been used for defining a concurrent semantics of several formalisms, from Petri nets to linear graph rewriting systems, which in turn lay at the basis of many visual frameworks. Stability however is restrictive for dealing with formalisms where a computational step can merge parts of the state, like graph rewriting systems with non-linear rules, which are needed to cover some relevant applications (such as the graphical encoding of calculi with name passing). We characterise, as a natural generalisation of prime algebraic domains, a class of domains that is well-suited to model the semantics of formalisms with fusions. We then identify a corresponding class of event structures, that we call connected event structures, via a duality result formalised as an equivalence of categories.We show that connected event structures are exactly the class of event structures that arise as the semantics of nonlinear graph rewriting systems. Interestingly, the category of general unstable event structures coreflects into our category of domains, so that our result provides a characterisation of the partial orders of configurations of such event structures.

链接与引用

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

BibTeX
@inproceedings{BaldanCG17,
  title = {Domains and event structures for fusions},
  author = {Paolo Baldan and Andrea Corradini and Fabio Gadducci},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005135}
}