paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Event Structures for Petri nets with Persistence

带持久性的 Petri 网的事件结构
LMCS vol.Volume 14, Issue 32018匹配度 2/10 · 该论文属于并发理论/形式语义方向,研究 Petri 网与事件结构的范畴论关系,虽涉及形式化验证的基础语义,但与用户关注的静态分析、LLM/Agent 交叉、浮点程序分析、贝叶斯程序分析等核心方向无直接关联。引用 9 inbox
Paolo Baldan, Roberto Bruni, Andrea Corradini, Fabio Gadducci, Hernan Melgratti, Ugo Montanari
crossref: 2026-09-10

AI 速览

一句话:将Petri网与事件结构的关系推广到析取因果,用持久库所刻画,并构造与局部连通事件结构的核反射链。

事件结构是并发建模的经典模型。Nielsen、Plotkin 与 Winskel 曾通过展开把安全 Petri 网映射到素事件结构:每个事件有唯一因果集,并可由配置域表示,范畴上形成核反射链。一般事件结构则允许析取因果,即事件可由不同的极小事件集使能。本文将 Petri 网与事件结构的联系扩展到析取因果:在网层面,析取因果由持久库所刻画,其中 token 一旦生成可多次使用而不被消耗,且多个 token 被整体解释、历史无关紧要。作者将普通网的结果推广到带持久性的 Petri 网,借助展开构造将其与一般事件结构的新子类——局部连通事件结构——相联系,并给出相应的核反射链。

问题
经典展开将安全 Petri 网对应到素事件结构,只能处理唯一因果;一般事件结构允许析取因果,但尚缺与 Petri 网扩展的对应。本文研究如何在网层面刻画析取因果并建立范畴联系。
方法
引入持久库所(token 不消耗且多 token 整体解释)来对应析取因果,定义展开构造,并证明带持久性 Petri 网与局部连通一般事件结构之间的核反射链。
评估
评估为理论性:通过构造展开与范畴论证明建立对应,给出核反射链,而非经验基准测试。
原文摘要(Abstract)

Event structures are a well-accepted model of concurrency. In a seminal paper by Nielsen, Plotkin and Winskel, they are used to establish a bridge between the theory of domains and the approach to concurrency proposed by Petri. A basic role is played by an unfolding construction that maps (safe) Petri nets into a subclass of event structures, called prime event structures, where each event has a uniquely determined set of causes. Prime event structures, in turn, can be identified with their domain of configurations. At a categorical level, this is nicely formalised by Winskel as a chain of coreflections. Contrary to prime event structures, general event structures allow for the presence of disjunctive causes, i.e., events can be enabled by distinct minimal sets of events. In this paper, we extend the connection between Petri nets and event structures in order to include disjunctive causes. In particular, we show that, at the level of nets, disjunctive causes are well accounted for by persistent places. These are places where tokens, once generated, can be used several times without being consumed and where multiple tokens are interpreted collectively, i.e., their histories are inessential. Generalising the work on ordinary nets, Petri nets with persistence are related to a new subclass of general event structures, called locally connected, by means of a chain of coreflections relying on an unfolding construction.

链接与引用

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

BibTeX
@article{paperbot372,
  title = {Event Structures for Petri nets with Persistence},
  author = {Paolo Baldan and Roberto Bruni and Andrea Corradini and Fabio Gadducci and Hernan Melgratti and Ugo Montanari},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 14, Issue 3},
  year = {2018},
  doi = {10.23638/lmcs-14(3:25)2018}
}