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

Rewriting with Frobenius.

Bonchi, F; Gadducci, F; Kissinger, A; Sobocinski, P; Zanasi, F; (2018) Rewriting with Frobenius. In: Dawar, A and Grädel, E, (eds.) Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. (pp. pp. 165-174). ACM: Oxford, United Kingdom. Green open access

[thumbnail of paperLICS18.pdf]
paperLICS18.pdf - Accepted version

Download (2MB) | Preview


Symmetric monoidal categories have become ubiquitous as a formal environment for the analysis of compound systems in a compositional, resource-sensitive manner using the graphical syntax of string diagrams. Recently, reasoning with string diagrams has been implemented concretely via double-pushout (DPO) hypergraph rewriting. The hypergraph representation has the twin advantages of being convenient for mechanisation and of completely absorbing the structural laws of symmetric monoidal categories, leaving just the domain-specific equations explicit in the rewriting system. In many applications across different disciplines (linguistics, concurrency, quantum computation, control theory,...) the structural component appears to be richer than just the symmetric monoidal structure, as it includes one or more Frobenius algebras. In this work we develop a DPO rewriting formalism which is able to absorb multiple Frobenius structures, thus sensibly simplifying diagrammatic reasoning in the aforementioned applications. As a proof of concept, we use our formalism to describe an algorithm which computes the reduced form of a diagram of the theory of interacting bialgebras using a simple rewrite strategy.

Type: Proceedings paper
Title: Rewriting with Frobenius.
Event: LICS '18
ISBN-13: 978-1-4503-5583-4
Open access status: An open access version is available from UCL Discovery
DOI: 10.1145/3209108.3209137
Publisher version: http://doi.acm.org/10.1145/3209108
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
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/10053250
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item