New foundations for string diagram rewriting

Add to your list(s) Download to your calendar using vCal

• Fabio Zanasi (UCL)
• Friday 02 June 2017, 11:00-12:00
• Computer Science Sloman Lounge.

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:

• Computer Science Departmental Series
• Computer Science Distinguished Seminars
• Computer Science Sloman Lounge
• Theoretical computer science seminar
• computer sience

Note that ex-directory lists are not shown.