We study rewriting for equational theories in the context of symmetric monoidal categories where there is a separable Frobenius monoid on each object. These categories, also called hypergraph categories, are increasingly relevant: Frobenius structures recently appeared in cross-disciplinary applications, including the study of quantum processes, dynamical systems and natural language processing. In this work we give a combinatorial characterisation of arrows of a free hypergraph category as cospans of labelled hypergraphs and establish a precise correspondence between rewriting modulo Frobenius structure on the one hand and double-pushout rewriting of hypergraphs on the other. This interpretation allows to use results on hypergraphs to ensure decidability of confluence for rewriting in a free hypergraph category. Our results generalise previous approaches where only categories generated by a single object (props) were considered.

Zanasi F. (2017). Rewriting in free hypegraph categories. OPEN PUBL ASSOC, SYDNEY, 00000, AUSTRALIA : Open Publishing Association [10.4204/EPTCS.263.2].

Rewriting in free hypegraph categories

Zanasi F.
2017

Abstract

We study rewriting for equational theories in the context of symmetric monoidal categories where there is a separable Frobenius monoid on each object. These categories, also called hypergraph categories, are increasingly relevant: Frobenius structures recently appeared in cross-disciplinary applications, including the study of quantum processes, dynamical systems and natural language processing. In this work we give a combinatorial characterisation of arrows of a free hypergraph category as cospans of labelled hypergraphs and establish a precise correspondence between rewriting modulo Frobenius structure on the one hand and double-pushout rewriting of hypergraphs on the other. This interpretation allows to use results on hypergraphs to ensure decidability of confluence for rewriting in a free hypergraph category. Our results generalise previous approaches where only categories generated by a single object (props) were considered.
2017
Proceedings of the 3rd Workshop on Graphs as Models, GaM 2017
16
30
Zanasi F. (2017). Rewriting in free hypegraph categories. OPEN PUBL ASSOC, SYDNEY, 00000, AUSTRALIA : Open Publishing Association [10.4204/EPTCS.263.2].
Zanasi F.
File in questo prodotto:
File Dimensione Formato  
paper (2).pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 743.39 kB
Formato Adobe PDF
743.39 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/904981
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact