UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Rewriting modulo symmetric monoidal structure

Bonchi, F; Gadducci, F; Kissinger, A; Sobocinski, P; Zanasi, F; (2016) Rewriting modulo symmetric monoidal structure. In: Koskinen, E and Grohe, M and Shankar, N, (eds.) LICS '16: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. (pp. pp. 710-719). ACM: New York, USA. Green open access

[img]
Preview
Text
Bonchi_Rewriting_modulo_symmetric_monoidal_AAM.pdf - Accepted version

Download (938kB) | Preview

Abstract

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. This paper lays a comprehensive foundation for this form of rewriting. We interpret diagrams combinatorially as typed hypergraphs and establish the precise correspondence between diagram rewriting modulo the laws of SMCs on the one hand and double pushout (DPO) rewriting of hypergraphs, subject to a soundness condition called convexity, on the other. This result rests on a more general characterisation theorem in which we show that typed hypergraph DPO rewriting amounts to diagram rewriting modulo the laws of SMCs with a chosen special Frobenius structure. We illustrate our approach with a proof of termination for the theory of non-commutative bimonoids.

Type: Proceedings paper
Title: Rewriting modulo symmetric monoidal structure
Event: LICS '16: Thirty-First Annual ACM/IEEE Symposium on Logic in Computer Science, 5–8 July 2016, New York, USA
ISBN-13: 9781450343916
Open access status: An open access version is available from UCL Discovery
DOI: 10.1145/2933575.2935316
Publisher version: https://doi.org/10.1145/2933575.2935316
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/1520754
Downloads since deposit
45Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item