![]() |
![]() |
University of Birmingham > Talks@bham > Theoretical computer science seminar > New foundations for string diagram rewriting
New foundations for string diagram rewritingAdd to your list(s) Download to your calendar using vCal
If you have a question about this talk, please contact Paul Taylor. String diagrams are a powerful and intuitive graphical syntax for terms of symmetric monoidal categories (SMCs). They find many applications in computer science and are becoming increasingly relevant in other fields such as physics and control theory. An important role in many such approaches is played by equational theories of diagrams, typically oriented and applied as rewrite rules. We establish a sound and complete interpretation for this form of rewriting in terms of double pushout (DPO) rewriting of hypergraphs, subject to a convexity condition. Non-convex rewriting in this domain is also interesting, as syntactically it corresponds to rewriting modulo a chosen separable Frobenius structure. Two further results strengthening this approach will be shown. The first is that, contrary to arbitrary hypergraph rewriting, with our setup confluence becomes decidable for terminating rewriting systems. The second is a sound and complete interpretation of commutative operators as additional Frobenius structures, which addresses the problem of non-termination of commutativity as a rewrite rule. This is joint work with Filippo Bonchi, Fabio Gadducci, Aleks Kissinger and Pawel Sobocinski. This talk is part of the Theoretical computer science seminar series. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other listsFilling in the blank – I will be ….... in 2050’ 'Roles' Postgraduate Gender and Sexuality Network Discussion Type the title of a new list hereOther talksThe tragic destiny of Mileva Marić Einstein Wave turbulence in the Schrödinger-Helmholtz equation Quantum Sensing in Space Control variates for computing transport coefficients Horizontal Mean Curvature Flow and stochastic optimal controls TBA |