Higher-Dimensional Subdiagram Matching

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 higherdimensional 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.

8 (Faces and cofaces). Let P be an oriented graded poset, x ∈ P , α ∈ +, -. The set of input (α = -) or output (α = +) faces of x is ∆ α x := y ∈ P | x covers y with orientation α .

The set of input (α = -) or output (α = +) cofaces of x is ∇ α x := y ∈ P | y covers x with orientation α .

We let ∆x := ∆ -x ∪ ∆ + x and ∇x := ∇ -x ∪ ∇ + x. 9 (Oriented Hasse diagram). Let P be an oriented graded poset. The oriented Hasse diagram of P is the directed graph ˚ H P whose

• set of vertices is the underlying set of P , and • for all vertices x, y, there is an edge from y to x if and only if y ∈ ∆ -x or x ∈ ∆ + y.

To represent an oriented graded poset P , we linearly order P n in each dimension n, so that each element x ∈ P is uniquely identified by a pair of integers (n, k), where n := dim x and k is the position of x in the linear order on P n . Then we represent P as a pair (face_data, coface_data) of arrays of arrays of pairs of sets of integers, where

here the index i ∈ 0, 1 is used to encode pairs, α(0) :=and α(1) := +. Sets of integers may be implemented as any data type supporting binary search in logarithmic time. Note that this representation is redundant: face_data and coface_data can be reconstructed from each other.

This is essentially an adjacency list representation of H P , with vertices separated according to their dimension, and incoming and outgoing edges separated according to their label. It is not unique: any permutation of the dimension-wise linear orders produces an equivalent representation.