\[apx:proofs\]]{}.

The rewriting formalism for graphs and graph-like structures that we use throughout the paper is the double-pushout (DPO) approach [@cmrehl:algebraic-approaches]. Although it was originally introduced for graphs [@DBLP:conf/focs/EhrigPS73], it is well-defined in any category $\C$. However, certain standard results for graph rewriting require that the category $\C$ has “good” properties. The category of graphs is an elementary topos—an extremely rich categorical structure—but weaker conditions on $\C$, for instance adhesivity, have been studied [@ls:adhesive-journal; @ehpp:adhesive-hlr; @ehrig2013categorical].

\[def:dpo-rewriting\] A *production* in $\C$ is a span of monos $L\lat~I\rat R$ in $\C$; the objects $L$ and $R$ are called left- and right-hand side, respectively.\

A *match* of a production $p\colon L\lat I \rat R$ to an object $X$ of $\C$ is a mono $m_L \colon L \rat X$ in $\C$. The production $p$ rewrites $X$ to $Y$ at $m_L$ (resp. the match $m_L$ to the *co-match* $m_R \colon R\to Y$) if the production and the match (and the co-match) extend to a diagram in $\C$, shown to the right, such that both squares are pushouts.

;

In this case, we write $X \oset{p,m_L}{\Longrightarrow} Y$ (resp. $(L\oset{m_L}{\rat} X) \oset{p}{\Rightarrow} (R\oset{m_R}{\to}
  Y)$). We also write $X \oset{p,m_L}{\Longrightarrow}$ and $X \oset{p}{\Rightarrow} Y$ if the specific 