Diana-Maria Kessler, the PhD student of the Department of Software Science, will defend his PhD thesis “Computational aspects of rewriting in higher-dimensional diagrams” (”Kõrgemamõõtmeliste diagrammide ümberkirjutamise arvutuslikud aspektid”) on June 27, 2025 starting at 14:00 (UTC +3 / Eastern European Time (EEST)). The defense will take place in School of Business and Educational Building room SOC-309 (Akadeemia tee 3, Tallinn) and can be also followed via Zoom.
Higher-dimensional rewriting is founded on the observation that certain rewrite systems correspond to directed cell complexes in different dimensions. This gives us a geometric grip on rewrite systems and rewrite derivations, connecting computational mathematics to higher categories and homotopy theory: rewrite systems are directed cell complexes and rewrite rules are directed homotopies.
In this thesis we adopt a computational perspective and view higher-dimensional rewriting as a model of computation in which an n-dimensional rewrite is a computation on (n − 1)-dimensional data. Our motivation is the question of whether such a model of computation would be a feasible one.
With this in mind, we start by studying the computational complexity of building diagrams in the setting of diagrammatic sets. One of the main results is a traversal algorithm for solving the isomorphism problem in time O(n2 log(n)). We continue by studying the higher-dimensional subdiagram matching problem for rewritable subdiagrams. We provide an algorithm for solving this problem in arbitrary dimension as well as an upper bound on its running time. In the general case, the problem turns out to be in NP. We further show that under certain acyclicity conditions (that are satisfied by all diagrams of dimension less than or equal to 3), the running time of the algorithm is polynomial in the size of the diagram.
The diagrams mentioned so far correspond to pasting diagrams. We end the thesis with the study of acyclicity conditions in a more general framework of diagrams. We show that under one of the acyclicity conditions that we study for the subdidiagram matching problem, the ω-category presented by a diagram shape is freely generated in the sense of polygraphs. We further show that under stronger acyclicity conditions this ω-category is equivalent to the one obtained from an augmented directed chain complex in the sense of Steiner, or consists only of subsets of cells in the diagram.
The thesis “Computational aspects of rewriting in higher-dimensional diagrams” is published in the Digital Collection of TalTech Library.
Supervisor(s):
- Prof. Amar Hadzihasanovic (TalTech)
- co-supervisor: Prof. Pawel Sobocinski (TalTech)
Opponents:
- Prof. Samuel Mimram, Ecole Polytechnique, France;
- Prof. Fabio Zanasi, University College London (UCL), United Kingdom.
Follow public defence via Zoom
Meeting ID: 913 8289 7259
Passcode: 660867