paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Graphical Affine Algebra

图形仿射代数
LICS 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2019匹配度 1/10 · 论文属于纯形式语义与图形代数方向,研究仿射连接子的完备公理化及其在电路/连接器语言中的应用;与用户关注的 LLM/Agent 交叉、机器学习系统静态分析、浮点程序分析、贝叶斯程序分析均无直接关联。虽涉及形式化与验证基础,但未触及用户核心问题。引用 41 inbox
Filippo Bonchi, Robin Piedeleu, Pawel Sobocinski, Fabio Zanasi
crossref: 2026-09-12

AI 速览

一句话:通过仿射连接子扩展图形线性代数,给出图形仿射代数在自然数模与域上模两类语义下的完备公理化。

图形线性代数是用于组合式推理线性计算设备的图解语言。本文为其引入仿射连接子,提出图形仿射代数,以刻画更丰富的仿射行为。该扩展虽简单却颇具表达力:当语义域为自然数模时可建模互斥等模式,当语义域为某类域上模时可建模非无源电子元件。作者的主要技术贡献是针对这两类解释给出完整的公理化,即建立可靠且完备的等式理论。案例研究进一步表明,图形仿射代数可刻画电路以及无状态连接子演算——一种面向分布式系统的协调语言。

问题
图形线性代数能组合式地推理线性计算设备,但无法直接表达仿射或非无源等更丰富的行为。
方法
引入仿射连接子,构造图形仿射代数,并针对自然数模与某类域上模两种语义域给出完整公理化。
评估
通过完备性证明以及电路与无状态连接子演算两个案例研究,验证其表达力与公理化。
原文摘要(Abstract)

Graphical linear algebra is a diagrammatic language allowing to reason compositionally about different types of linear computing devices. In this paper, we extend this formalism with a connector for affine behaviour. The extension, which we call graphical affine algebra, is simple but remarkably powerful: it can model systems with richer patterns of behaviour such as mutual exclusion-with modules over the natural numbers as semantic domain-or non-passive electrical components-when considering modules over a certain field. Our main technical contribution is a complete axiomatisation for graphical affine algebra over these two interpretations. We also show, as case studies, how graphical affine algebra captures electrical circuits and the calculus of stateless connectors-a coordination language for distributed systems.

链接与引用

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

BibTeX
@inproceedings{paperbot5019,
  title = {Graphical Affine Algebra},
  author = {Filippo Bonchi and Robin Piedeleu and Pawel Sobocinski and Fabio Zanasi},
  booktitle = {LICS},
  year = {2019},
  doi = {10.1109/lics.2019.8785877}
}