Higher-dimensional subdiagram matching
From MaRDI portal
Publication:6433538
arXiv2304.09216MaRDI QIDQ6433538FDOQ6433538
Author name not available (Why is that?), Amar Hadzihasanovic
Publication date: 18 April 2023
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.
Strict omega-categories, computads, polygraphs (18N30) Tricategories, weak (n)-categories, coherence, semi-strictification (18N20) Computational methods for problems pertaining to manifolds and cell complexes (57-08)
This page was built for publication: Higher-dimensional subdiagram matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433538)
