paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Monoidal Width

幺半宽度
LMCS vol.Volume 19, Issue 32023匹配度 2/10 · 论文属于范畴论/形式语义领域,提出 monoidal width 作为态射复杂度度量,与用户关注的静态分析、Agentic 程序、LLM 与形式化验证交叉等核心方向无直接关联;且缺乏工程实现、工业落地和问题驱动,未涉及 LLM。引用 2 inbox
Elena Di Lavore, Paweł Sobociński
crossref: 2026-09-10

AI 速览

一句话:提出幺半宽度,作为幺半范畴中态射的复杂度度量,通过幺半分解惩罚大对象复合,统一刻画树宽、秩宽与矩阵秩。

论文引入“幺半宽度”作为幺半范畴中态射复杂度的度量。受图的结构宽度(如树宽、秩宽)启发,该度量基于语法分解:态射的幺半分解是使用幺半积与复合运算书写该态射的表达式;它惩罚沿“大”对象的复合,同时鼓励使用幺半积。作者证明,通过为图选择适当的范畴代数进行分解,可以分别刻画树宽与秩宽;对于矩阵,幺半宽度与秩相关。这些结果表明,幺半宽度可作为以幺半范畴态射建模的过程的结构复杂度度量。

问题
如何为幺半范畴中的态射定义一种类似图结构宽度的复杂度度量,并统一刻画树宽、秩宽等已有度量。
方法
基于语法分解,允许用幺半积和复合构造态射,惩罚沿大对象的复合、奖励幺半积,从而定义幺半宽度,并为具体结构选择合适的范畴代数。
评估
通过理论案例证明该度量可捕获图的树宽与秩宽,并揭示矩阵的幺半宽度与秩相关。
原文摘要(Abstract)

We introduce monoidal width as a measure of complexity for morphisms in monoidal categories. Inspired by well-known structural width measures for graphs, like tree width and rank width, monoidal width is based on a notion of syntactic decomposition: a monoidal decomposition of a morphism is an expression in the language of monoidal categories, where operations are monoidal products and compositions, that specifies this morphism. Monoidal width penalises the composition operation along ``big'' objects, while it encourages the use of monoidal products. We show that, by choosing the correct categorical algebra for decomposing graphs, we can capture tree width and rank width. For matrices, monoidal width is related to the rank. These examples suggest monoidal width as a good measure for structural complexity of processes modelled as morphisms in monoidal categories.

链接与引用

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

BibTeX
@article{paperbot2195,
  title = {Monoidal Width},
  author = {Elena Di Lavore and Paweł Sobociński},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 19, Issue 3},
  year = {2023},
  doi = {10.46298/lmcs-19(3:15)2023}
}