3D pasting and the meaning of associativity

Abstract

Higher-dimensional category theory has had an increasing role in the semantics of computation with, for example, the rise of homotopy type theory, the importance of higher-dimensional rewriting, and the analysis of distributed systems and concurrency. An important tool of category theory is diagrammatic reasoning, and in higher-dimensional categories that reasoning frequently involves working with pasting diagrams. One- and two-dimensional pasting diagrams are well understood, but the subtleties that arise with three-dimensional pasting diagrams are less well known and much less studied. We define and explore associativity of pasting composition in three-dimensional categories, explaining why it is significantly more complex than that for two-dimensional categories. We give a new, mildly improved, geometric formulation for the notion of two-dimensional pasting. We refocus and further develop the topic of three-dimensional pasting. In particular, we study a specific example of a three-dimensional pasting scheme in order to explain the delicacy of composition, especially its associativity, for three dimensions and beyond. The example demonstrates that in the three-dimensional case, the independent computation of sub-diagrams can, in contrast to one- and two-dimensional pasting, lead to deadlock. This has important implications for the analysis of three-dimensional pasting compositions and for strategies for efficient computation and concurrent processing.