paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Relating Reversible Petri Nets and Reversible Event Structures, categorically

可逆Petri网与可逆事件结构的范畴论关联
LMCS vol.Volume 21, Issue 22025匹配度 1/10 · 该论文属于并发理论/形式语义中的可逆Petri网与事件结构范畴化研究,虽与形式化方法相邻,但不涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析等用户核心方向。引用 2 inbox
Hernán Melgratti, Claudio Antares Mezzina, G. Michele Pinna
crossref: 2026-09-10

AI 速览

一句话:将因果网扩展以刻画非对称冲突,并范畴化可逆Petri网与可逆非对称事件结构的关系。

因果网(Causal Nets, CNs)是一类通过抑制弧刻画因果依赖的Petri网,在表示并发与分布式系统行为时扮演出现网的角色,即便在可逆计算场景下亦然。本文对CNs进行扩展,使其能够刻画非对称冲突,并在此基础上研究两方面问题:(i) 如何将这类扩展网及其可逆版本组织为一个范畴;(ii) 它们与可逆非对称事件结构(reversible asymmetric event structures)范畴之间的关系。作者采用范畴论方法给出网与事件结构之间的对应构造,揭示了两种可逆并发模型在语义层面的联系,为可逆并发系统的统一语义框架提供了理论基础。

问题
可逆并发系统中,因果网(CNs)虽能刻画因果依赖,却无法表达非对称冲突;同时,可逆Petri网与可逆事件结构之间的语义对应关系尚不清晰。
方法
扩展因果网以支持非对称冲突,将扩展后的网及其可逆版本构造为范畴,并借助范畴论工具建立其与可逆非对称事件结构范畴之间的关系。
评估
通过范畴构造与函子关系的形式化证明,论证两类可逆并发模型之间的对应与语义联系。
原文摘要(Abstract)

Causal nets (CNs) are Petri nets where causal dependencies are modelled via inhibitor arcs. They play the role of occurrence nets when representing the behaviour of a concurrent and distributed system, even when reversibility is considered. In this paper we extend CNs to account also for asymmetric conflicts and study (i) how this kind of nets, and their reversible versions, can be turned into a category; and (ii) their relation with the categories of reversible asymmetric event structures.

链接与引用

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

BibTeX
@article{MelgrattiMP25,
  title = {Relating Reversible Petri Nets and Reversible Event Structures, categorically},
  author = {Hernán Melgratti and Claudio Antares Mezzina and G. Michele Pinna},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 21, Issue 2},
  year = {2025},
  doi = {10.46298/lmcs-21(2:20)2025}
}