# Rewriting in Free Hypergraph Categories

arXiv: https://arxiv.org/abs/1712.09495 · HTML: https://mlsanity.com/paper/1712.09495/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Dec 2017.

## Built on by (most cited first, 1 of 1)

- [Reverse Derivative Ascent: A Categorical Approach to Learning Boolean Circuits](https://mlsanity.com/paper/2101.10488/) (2021)

## Abstract (arXiv)

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.