paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Higher-Dimensional Subdiagram Matching

高维子图匹配
LICS 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2023匹配度 2/10 · 该论文属于高阶重写与范畴论/同伦论交叉的形式语义研究,核心是 diagrammatic sets 中的子图匹配算法与复杂度,与用户关注的程序静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析均无直接关系。仅在“形式化方法/重写理论”这一非常宽泛的层面上有微弱关联。引用 8 inbox
Amar Hadzihasanovic, Diana Kessler
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:在图表集合框架下研究高维图重写中的子图匹配问题,给出任意维匹配算法及其复杂度界。

高维重写建立在重写系统与胞腔复形的对偶之上:重写规则两侧是某个 (n+1)-胞腔边界的两个 n-胞腔图。本文在图表集合(diagrammatic sets)的组合框架中,把高维图重写视为一种计算机制,重点研究可重写子图的匹配问题。作者基于图的层化(layering)新结果,提出任意维度的子图匹配算法,并推导其时间复杂性上界;进一步证明在特定无环条件下,这些超多项式上界可改进为多项式界,且该条件一般对不超过 3 维的图成立,最后讨论 4 维时出现的挑战。

问题
如何高效匹配高维图重写中的可重写子图,并刻画该匹配问题的时间复杂度。
方法
在 diagrammatic sets 的组合框架下,利用图的层化新结果,给出任意维度的子图匹配算法,并分析其上界与无环条件下的多项式界。
评估
理论分析:推导一般超多项式上界,并在无环条件下改进为多项式界;证明该条件对不超过 3 维的图普遍成立,并讨论 4 维的挑战。
原文摘要(Abstract)

Higher-dimensional rewriting is founded on a duality of rewrite systems and cell complexes, connecting computational mathematics to higher categories and homotopy theory: the two sides of a rewrite rule are two halves of the boundary of an (n + 1)-cell, which are diagrams of n-cells. We study higher-dimensional diagram rewriting as a mechanism of computation, focussing on the matching problem for rewritable subdiagrams within the combinatorial framework of diagrammatic sets. We provide an algorithm for subdiagram matching in arbitrary dimensions, based on new results on layerings of diagrams, and derive upper bounds on its time complexity. We show that these superpolynomial bounds can be improved to polynomial bounds under certain acyclicity conditions, and that these conditions hold in general for diagrams up to dimension 3. We discuss the challenges that arise in dimension 4.

链接与引用

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

BibTeX
@inproceedings{abs-2304-09216,
  title = {Higher-Dimensional Subdiagram Matching},
  author = {Amar Hadzihasanovic and Diana Kessler},
  booktitle = {LICS},
  year = {2023},
  doi = {10.1109/lics56636.2023.10175726}
}