paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Diagrammatic algebra: from linear to concurrent systems

图解代数:从线性系统到并发系统
POPL 3(POPL)2019匹配度 1/10 · 该论文属于并发系统、图表代数与范畴论形式语义,和用户画像关注的 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析没有直接关联;仅在形式化方法层面存在极弱交集。引用 51 inbox
Filippo Bonchi, Joshua Holland, Robin Piedeleu, Paweł Sobociński, Fabio Zanasi
crossref: 2026-09-10

AI 速览

一句话:提出资源演算,一种图表式并发语言,用自然数替换信号流演算中的实数,并以等式理论刻画其可定义行为。

论文关注如何以统一的图解代数框架刻画并发系统行为。作者提出资源演算,一种弦图式语言,其语法与操作语义继承自信号流演算;关键观察是,将操作语义中的实数(表示信号)替换为自然数(表示资源),即可涌现并发行为模式。作者为资源演算及其带状态扩展建立等式理论,并通过范畴同构精确刻画可定义行为空间,即加法关系的凸代数宇宙。最后证明该演算足以捕获经典 Petri 网可定义的行为。

问题
如何为并发系统提供一种与线性信号流演算同源的图解代数语言,并精确刻画其可定义行为?
方法
引入资源演算,沿用信号流演算的语法与操作语义,将实数信号替换为自然数资源;为其及带状态扩展构造等式理论,并用范畴同构连接可定义行为空间。
评估
通过范畴同构证明等式理论能刻画演算的可定义行为,并证明该演算足以表达经典 Petri 网可定义的行为。
原文摘要(Abstract)

We introduce the resource calculus, a string diagrammatic language for concurrent systems. Significantly, it uses the same syntax and operational semantics as the signal flow calculus --- an algebraic formalism for signal flow graphs, which is a combinatorial model of computation of interest in control theory. Indeed, our approach stems from the simple but fruitful observation that, by replacing real numbers (modelling signals) with natural numbers (modelling resources) in the operational semantics, concurrent behaviour patterns emerge. The resource calculus is canonical: we equip it and its stateful extension with equational theories that characterise the underlying space of definable behaviours---a convex algebraic universe of additive relations---via isomorphisms of categories. Finally, we demonstrate that our calculus is sufficiently expressive to capture behaviour definable by classical Petri nets.

链接与引用

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

BibTeX
@article{paperbot632,
  title = {Diagrammatic algebra: from linear to concurrent systems},
  author = {Filippo Bonchi and Joshua Holland and Robin Piedeleu and Paweł Sobociński and Fabio Zanasi},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {3},
  number = {POPL},
  year = {2019},
  doi = {10.1145/3290338}
}