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