{'fraction_non_alphanumeric': 0.0374066777270842, 'fraction_numerical': 0.005888191029211353, 'mean_word_length': 4.21621464997682, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 57, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Rewriting Context-free Families of String Diagrams

String diagrams provide a convenient graphical framework which may be used for equational reasoning about morphisms of monoidal categories. However, unlike term rewriting, rewriting string diagrams results in shorter equational proofs, because the string diagrammatic representation allows us to formally establish equalities modulo any rewrite steps which follow from the monoidal structure. Manipulating string diagrams by hand is a time-consuming and error-prone process, especially for large string diagrams. This can be ameliorated by using software proof assistants, such as Quantomatic. However, reasoning about concrete string diagrams may be limiting and in some scenarios it is necessary to reason about entire (infinite) families of string diagrams. When doing so, we face the same problems as for manipulating concrete string diagrams, but in addition, we risk making further mistakes if we are not precise enough about the way we represent (infinite) families of string diagrams. The primary goal of this thesis is to design a mathematical framework for equational reasoning about infinite families of string diagrams which is amenable to computer automation. We will be working with context-free families of string diagrams and we will represent them using context-free graph grammars. We will model equations between infinite families of diagrams using rewrite rules between context-free grammars. Our framework represents equational reasoning about concrete string diagrams and context-free families of string diagrams using double-pushout rewriting on graphs and context-free graph grammars respectively. We will prove that our representation is sound by showing that it respects the concrete semantics of string diagrammatic reasoning and we will show that our framework is appropriate for software implementation by proving important decidability properties.


Introduction
A monoidal category is a category C which is equipped with a special object I ∈ C, called the monoidal unit, and also a bifunctor ⊗ : C × C → C, which is associative and unital, called the tensor product. Like any other category, two morphisms f and g may be composed in the usual way f • g, provided they are compatible, but they may also be composed in another, orthogonal way, using the tensor product: f ⊗ g.
Monoidal categories are defined at a high level of abstraction and they have found applications in many different fields. For example, in linguistics they can be used to provide the compositional semantics for sentences [8], in concurrency theory, monoidal categories describe the structure of Petri nets with boundary [49], in control theory they can be used to study signal-flow graphs [6,5,3] and in categorical quantum mechanics [1], monoidal categories provide the basic framework for all developments in the field and have been used to design diagrammatic calculi for quantum computation, such as the ZX-calculus [10,9].
In any monoidal category, we can prove: (1.0.1) and the proof involves a few simple steps: where we have used the interchange law, which is not an axiom of monoidal categories, but a theorem which follows from its axioms (assuming the axiomatisation given in [39], also cf. proof of Equation (2.3.2)). However, instead of using terms like we did above, the same fact can be established in an intuitively simpler way if we use string diagrams: String diagrams [29] are two-dimensional graph-like structures which can be used to formally reason about monoidal categories in a sound and complete way -an equation between two morphisms in a monoidal category follows from the monoidal data iff the two string diagrams which represent these morphisms are isotropic, that is, one can be continuously deformed into the other. In the example above, we can see that by sliding the boxes up or down the wires, we can obtain one diagram from the other.
String diagrams may be used as an alternative to the standard term-based approach for equational reasoning in monoidal categories. One of the advantages provided by doing so is that equational reasoning may be done modulo any equality which follows from the monoidal axioms. As a result, by using string diagrams, equational proofs are shorter compared to proofs using term rewriting, because rewrite steps which follow from the monoidal structure are absorbed into the diagrammatic formalism. This also allows us to focus on the additional structure provided by the model category in which we are working in (that is, any structure on top of the monoidal one).
A particular example of a string diagrammatic theory is the ZX-calculus. It is a diagrammatic calculus which may be used to reason about quantum computation and information. Unlike the standard language for quantum computing which is based on the Hilbert space formalism, the ZX-calculus is described via string diagrams. The underlying monoidal category is FdHilb, the category of finite dimensional Hilbert spaces and linear maps. The standard presentation of the syntax of the ZX-calculus [10] includes generators of the form: If the labels α of the generators are allowed to range over [0, 2π), then the ZXcalculus is universal for quantum computation, meaning it can exactly represent any morphism in FdHilb. However, in that case it is also incomplete [51], meaning that using its equational rules we cannot prove all true equalities in FdHilb. However, if we restrict the labels α to the integer multiples kπ/4 in [0, 2π), then the calculus is approximately universal and complete for an important segment of quantum computing, called Stabilizer Quantum Mechanics [2] and has many applications for Fault-Tolerant Quantum Computation [26]. We will use this version of the ZX-calculus as motivation for some of the constructions in this thesis and we will often provide examples using it in order to illustrate more abstract concepts that we develop. Equational reasoning in the ZX-calculus is done by manipulating diagrams, instead of using linear algebra like in the traditional language for quantum computing. For example, a well-known fact in quantum computing is that the composition of two CNOT gates is the identity. The standard way of proving this in the traditional language is by evaluating the matrix representation of the composition, which in this case consists of multiplying two 4 × 4 matrices: with respect to the axioms of the ZX-calculus. The monoidal structure of FdHilb is captured by the string diagrammatic nature of the calculus and the additional structure of FdHilb is captured by the equational axioms of the ZX-calculus. Rewriting diagrams in the ZX-calculus, with respect to its axiomatic rules, then corresponds to equational reasoning in FdHilb modulo any equational step which follows from the monoidal structure (such as the interchange law from above).
The shorter equational proofs is not the only advantage of using string diagrams for reasoning about monoidal categories. Composition of morphisms in a monoidal category is inherently two-dimensional -morphisms can be composed using the standard categorical composition (− • −) or the tensor product (− ⊗ −). However, the term-based syntax for writing down morphisms is one-dimensional -we write our compositions on a line and we have to use brackets in order to correctly specify the order in which the composition operations need to be performed. Another advantage of using string diagrams is that their syntax captures the compositional relations of monoidal categories in a more intuitively clear way. We can see this even for simple cases -compare the term-based syntax of (1.0.1) with the string diagrammatic syntax of (1.0.2). The difference becomes even more pronounced when considering larger terms. For example, for morphisms f : A → A ⊗ C, g : B ⊗ C → B ⊗ D, h : A ⊗ C → C, k : D → B, compare: Equational reasoning with string diagrams is done via subdiagram substitution.
Given an equational rule between two string diagrams, one side of the rule is matched onto a subdiagram of some target diagram which we wish to rewrite, and the matched part is then replaced with the other side of the equational rule. For example, in rewrite step (4) of (1.0.4) above, the rule which is applied is simply: = However, rewriting large diagrams in such a way may involve many non-trivial rewrite steps [52]. Doing this by hand has several disadvantages: the process could take a long time, manually creating the diagrams at each step is tedious and it is possible to commit errors when a rewrite rule is not applied correctly. To avoid this, it is preferable to use a software proof assistant like Quantomatic [36] which can assist with the reasoning process. Internally, Quantomatic uses a discrete representation of string diagrams, called string graphs [31], which represents string diagrams as special kinds of labelled graphs and then string diagram rewriting is represented by the wellestablished graph transformation approach called double-pushout rewriting [11,21].
Quantomatic is a diagrammatic proof assistant. It has a graphical user interface which allows users to define their own theories based on string diagrams and also to create and edit string diagrams and string diagram rewrite rules. Quantomatic supports two ways of rewriting string diagrams -user-guided, where users may apply rewrite rules at each step of the derivation, or fully automated rewriting, where multiple rewrite steps are performed by Quantomatic in accordance to user-defined tactics.
Moreover, users may mix both approaches and the software allows them to explore multiple rewrite sequences. There are also useful export options -diagrams, rewrite rules and entire derivations may be exported as Tikz code ready to be embedded in a LaTeX document and they may also be easily exported as interactive HTML5 elements within a webpage. All of these features make Quantomatic a useful tool for equational reasoning about string diagrams as it reduces the amount of time needed to manipulate them and greatly reduces the possibilities of errors being introduced during the derivation process.
Aside from rewriting string diagrams one at a time, in many scenarios it is useful, and sometimes necessary, to rewrite entire families of string diagrams. By rewriting a single string diagram using some equational rule, we establish an equality between two string diagrams which therefore represents an equality between two morphisms in the category in which we are reasoning. However, in this thesis we will show that we can do equational reasoning for string diagrams at a higher level. A family of string diagrams is an (infinite) set of string diagrams which are related in some way.
When rewriting a family of diagrams, we establish an equational schema, that is we establish (infinitely) many different equalities which relate pairs of string diagrams and thus morphisms. Reasoning in this way is strictly more general and then specific equalities between string diagrams follow as special cases of an equational schema.
We will give examples from the ZX-calculus to illustrate these ideas. To begin with, the standard presentation of the syntax of the ZX-calculus [10] includes gen- Moreover, reasoning on this level is sometimes necessary. For example, quantum algorithms and protocols are usually described in terms which allow for input of arbitrary size. Therefore, if we wish to reason about them using the ZX-calculus, then we have to be able to talk about families of ZX-diagrams. The primary focus of this thesis is the study of infinite families of string diagrams, and in particular, the formal methods which could be used to do equational reasoning with them. We will not restrict ourselves to the ZX-calculus or any other specific theory. Instead, we will study this problem in generality -we only assume that our string diagrams can be labelled over finite alphabets of node and wire labels, and we will show how we can do equational reasoning for certain infinite families of string diagrams.
When working with large families of string diagrams (in terms of the number of nodes and edges required to depict them) we face the same problems as with working with large concrete string diagrams. Therefore, ideally, we would wish to be able to perform the reasoning process using software support. However, when describing families of string diagrams so far, we have been rather informal. We described these families using the (· · · ) notation. While this notation is intuitive, it is not precise enough for computer implementation. Therefore, if we wish to work with infinite families of string diagrams using a proof assistant, then we need to be able to describe these families using a formal notation.
Quantomatic does support reasoning with certain infinite families of string diagrams. These families are described by the theory of !-graphs, pronounced, bang graphs. !-graphs, as the name suggests, are special kinds of graphs. They are strictly more general compared to string graphs. Instead of using the (· · · ) notation, families of string diagrams are denoted by marking subgraphs of a string graph with !-boxes, which are graphically depicted by drawing a blue box around the required subgraph. The subgraphs which are marked by !-boxes are allowed to be copied an arbitrary number of times while preserving the connection relations with the rest of the graph. This is the mechanism used by !-graphs in order to represent infinite families of string diagrams. For example, in Quantomatic we can depict a !-graph in the following way: and it is interpreted as the family of diagrams on the left-hand side of (1.0.8). More formally, it is the set: Then, an equational schema between two families of string diagrams is represented by a pair of !-graphs with a bijective correspondence between their !-boxes. For example, the equational schema (1.0.8) is represented by: Finally, equational reasoning between entire (infinite) families of string diagrams is represented by double-pushout (DPO) rewriting of !-graphs. Quantomatic fully supports this kind of rewriting and provides features for fully automated and user-guided rewriting of families of diagrams.
However, the !-graph formalism is limited in terms of its expressive power. !-graphs can only represent families of string diagrams which are of bounded diameter, meaning that there is a fixed upper bound on the shortest distance between any pair of nodes in its diagrams. In the context of the ZX-calculus, this is very limiting, because it means that any protocol or algorithm whose time-complexity is not constant cannot be described via !-graphs. Another limitation is that !-graphs can only represent families of string diagrams which are finitely colourable. For example, this means that !-graphs cannot represent any family of string diagrams which contain a clique of arbitrary size. In the context of the ZX-calculus this means that we cannot represent the local complementation rule of [20], given by: where K n−1 denotes the totally connected graph on n − 1 green vertices connected to each other via Hadamard (H) gates. This rule is very important as it is used in the only known decision procedure for equality of stabilizer operations in the ZX-calculus [2]. In fact, one of the initial design goals for the !-graph formalism was precisely this -the ability to represent the local complementation rule of the ZX-calculus. 1 Our primary motivation in this thesis is to develop an alternative to the !-graph formalism which avoids some of its limitations in terms of expressive power, while retaining as many of its useful features as possible. In particular, we wish to be able to do equational reasoning on infinite families of string diagrams in a formal way which can be implemented in Quantomatic, or other software proof-assistants. Of course, as with any other language generating device, there is a tradeoff between expressive power on one side and decidability, complexity and structural properties on the other.
The alternative which we propose is based on (slightly extended) context-free graph grammars [24], which avoid both of the limitations of !-graphs described above. These grammars are a generalisation of the standard context-free grammars on strings.
However, context-free graph grammars (CFGGs) generate languages of graphs, not strings, and they are strictly more powerful than the standard context-free string grammars. Both CFGGs and !-graphs can generate languages of graphs, but as we shall show, the classes of languages which they induce are incomparable -there are !-graph languages which cannot be represented using CFGGs and vice-versa. 1 Ross Duncan. Personal communication.
In particular, the alternative grammars to !-graphs which we shall study are called B-ESG grammars, which is a shorthand for Boundary Encoded String Graph grammars. B-ESG grammars are a special kind of CFGGs with a simple extension which allows us to encode some additional graph structure in specially labelled edges. An example of a B-ESG grammar which represents the local complementation rule of Equation (1.0.9) is given by: This is a compact representation of a very powerful and complicated derived rule of the ZX-calculus which !-graphs cannot express. In later chapters, we will describe in detail how B-ESG grammars work and how they can represent equational rules of the ZX-calculus.
We will show that our proposed alternative is strictly more expressive than an important class of !-graphs, called !-graphs with trivial overlap. The author does not know of any !-graph languages of interest for practical applications outside of that class, so the proposed alternative is suitable in terms of expressive power for current known uses. We also show how B-ESG grammars can be used to represent equational schemas between infinite context-free families of string diagrams. Our proposed framework also supports rewriting infinite families of string diagrams using already established equational schemas. All of our rewrites are kept sound in the sense that they respect the concrete semantics of the equational schemas and families of diagrams used in the rewrites. Moreover, because we are also interested in implementing software support for our framework, we keep all of our constructions decidable.
The rest of the thesis is structured as follows. In Chapter 2, we introduce all of the relevant background theory. This includes an introduction to adhesive and partially adhesive categories which show how to do DPO rewriting. DPO rewriting is the graph transformation mechanism which we use in order to model equational reasoning, both for string diagrams and also for families of string diagrams. We also describe string diagrams and their discrete representation, string graphs, in sufficient detail. We then give a more detailed introduction to families of string diagrams and In Chapter 5, we begin by showing that DPO rewriting is well-behaved for B-edNCE grammars. We then show how to rewrite B-edNCE grammars using DPO rewriting, such that the rewrites are sound with respect to the concrete semantics, that is, any concrete instance of our grammar rewrites corresponds to a sequence of concrete rewrite rules from the equational schemas we are representing. These techniques are then extended to B-ESG grammars by showing that we can rewrite B-ESG grammars using B-ESG rewrite rules in a sound way. In terms of string diagrams, this shows that we can do equational reasoning on context-free families of string diagrams using equational schemas where both sides of the schema are also a context-free family of diagrams.
Finally, in Chapter 6, we provide some concluding remarks and discuss future work.

Chapter 2 Background
In Section 2.1, we introduce adhesive categories, which are categories suitable for doing double-pushout (DPO) rewriting. Specific instances of adhesive categories which are presented are Set and MultiGraph -the categories of sets and multigraphs respectively.
However, in this thesis, we will also be doing DPO rewriting in categories which are not adhesive. In Section 2.2, we will describe partially adhesive categories, which are categories where DPO rewriting behaves exactly like DPO rewriting in their ambient adhesive category, provided that the rewrite rules and matchings satisfy additional conditions. Graph, the category of graphs where parallel edges are not allowed, is an example of a partially adhesive category (with ambient adhesive category MultiGraph) which is discussed.
In Section 2.3, we introduce string diagrams, which are the primary objects which we wish to reason about. We describe their relationship to (traced symmetric) monoidal categories and then introduce a discrete representation of string diagrams, called string graphs, which we shall use as it is more straightforward to build a proof assistant on top of this theory. We also describe the partially adhesive structure of string graphs.
We proceed by introducing families of string diagrams in Section 2.4 and show how we can reason about infinitely many string diagrams at the same time, instead of just concrete string diagrams. We also describe !-graphs which provide for a formal and finite way to represent certain infinite families of string graphs (and thus string diagrams).
Finally, in Section 2.5, we provide an introduction to context-free graph grammars.
This is the main mechanism which we use in order to represent families of string graphs, as an alternative to !-graphs, in later chapters and most of the original results are stated for these grammars.

Adhesive Categories
Adhesive categories were introduced by Lack and Sobocinski in [38]. Adhesive categories establish a categorical framework which generalises the standard method of doing double-pushout (DPO) rewriting on graphs. Because of the high level of abstraction on which adhesive categories are defined, DPO rewriting can be performed on any category which is shown to satisfy their axioms and the rewrites retain important properties enjoyed by DPO rewriting on graphs, such as the Local Church-Rosser Theorem and the Concurrency Theorem.
Adhesive categories fit in very nicely in the context of this thesis. We will be doing DPO rewriting on both graphs and edNCE grammars both of which will be based on two different graph models. DPO rewriting over graphs is well-known, but it has not been studied in the context of edNCE grammars. So, instead of showing how DPO rewriting works in each of those cases, we will recall how DPO rewriting can be performed in adhesive categories where it has already been demonstrated. To make use of these results, we will show that the specific categories we are interested in are adhesive (or partially adhesive, see Section 2.2) and then DPO rewriting along with several useful lemmas follow as a result in each of our model categories.
In this section, we will introduce all of the definitions and propositions related to adhesive categories and DPO rewriting that we will need in the rest of the thesis. We begin by providing the formal definition for an adhesive category. Kampen square is and for this reason we will not provide a formal definition.
We will also not make any further references to pullbacks either, so the only important part of the definition (in the context of this thesis) is that pushouts along monomorphisms always exist. To show that the categories we are interested in are adhesive, we will consider a few well-known examples of adhesive categories and then we will make use of two lemmas which show that adhesive categories are closed under certain categorical constructions. These lemmas and one of the examples are provided below.
Lemma 2.1.3 ( [38]). If C is adhesive then so are C/C and C/C for any object C of C.
These two lemmas are powerful and they allow us to easily prove adhesivity of some of the categories we are interested in. We shall illustrate this now by proving that the category of labelled multigraphs is adhesive, which is well-known and pointed out in [38]. This definition is standard in the graph transformation literature. An object of UMultiGraph consists of a set of vertices (V ), a set of edges (E) and two functions s (source) and t (target) which assign the source and target vertices to edges. Note, that the graphs in this category may have self-loops and parallel edges (also frequently called multiple edges). For this reason, we will refer to them as unlabelled multigraphs.
We will later introduce graphs which are just labelled multigraphs which do not have any self-loops and any pair of parallel edges needs to have different labels. Now we can easily prove that this category is adhesive. We can extend our multigraphs by introducing labels. A labelled multigraph is a multigraph where there are two labelling functions which assign labels to the vertices and edges of the multigraph. of UMultiGraph, which in addition respects the labelling, that is the following diagrams commute: Labelled multigraphs are strictly more general than unlabelled multigraphs -by choosing singleton sets for the vertex and edge label alphabets Σ and Γ, we get UMultiGraph ∼ = MultiGraph Σ,Γ . We will be working with labelled multigraphs from now on, so for brevity we will simply refer to them as multigraphs. If the alphabets Σ and Γ are clear from the context, then we will simply write MultiGraph for the category of labelled multigraphs over Σ and Γ. If H ∈ MultiGraph, then we shall denote with [H] the set of all multigraphs isomorphic to H. Lemma 2.1.8. MultiGraph Σ,Γ is adhesive.
Proof. Consider the category of typed multigraphs UMultiGraph/T, where T ∈ UMultiGraph is the multigraph given by: The typing graph T in the above definition has vertices given by the vertex label alphabet Σ and for each pair of vertices (u, v) and each edge label γ ∈ Γ, there is an edge from u to v with label γ. Thus, an object in the slice category UMultiGraph/T assigns a vertex label to each vertex and an edge label to each edge with no further restrictions. It is well-known (and easy to see) that MultiGraph Σ,Γ is isomorphic to the slice category UMultiGraph/T [4]. Therefore MultiGraph Σ,Γ is adhesive by In a similar way, by making use of these two lemmas, we will later show that the category of multi-edNCE grammars is adhesive.
Adhesive categories can be used in order to understand rewriting for certain kinds of structures. One of the most basic notions related to that is the notion of a rewrite rule. It can be defined in an arbitrary category, not necessarily an adhesive one.
Intuitively, a rewrite rule consists of a left-hand side object, a right-hand side object and a third object which appears as a subobject in both of them. We shall refer to L as the left-hand side of the rule, R as the right-hand side and I as the interface of the rule. In the literature, rewrite rules (or productions in DPO grammars) are sometimes defined simply as a span. However, some of the important theorems and lemmas about adhesive categories only hold for spans over monomorphisms. In addition, we will only consider rewrite rules consisting of a pair of monomorphisms and for this reason we choose the above definition. We will use rewrite rules in appropriate categories in order to encode equations (equational schemas) between string diagrams (families of string diagrams).
Next, we consider a lemma which relates the monomorphisms of a span to their counterparts in a pushout square. Therefore, in any adhesive category, given a span of monomorphisms, the pushout is guaranteed to exist and will consist of four monomorphisms. All of the pushouts that we will consider in the main body of the thesis will be over monomorphisms and this lemma will help us to establish that.
Next, we will introduce the notion of pushout complement. Intuitively, it can be thought of as an operation where we subtract a part L from another object H while preserving a third part I which is shared by both objects. Unlike the pushout, a pushout complement is not a universal construction in category theory. A pushout complement is not necessarily unique and in certain categories there can be two or more non-isomorphic objects that form a pushout complement. However, adhesive categories ensure that pushout complements are indeed unique (up to isomorphism) when they are computed over monomorphisms. We will only consider pushout complements and pushouts where all morphisms are monomorphisms and therefore the following lemma is of great importance.
Lemma 2.1.12 ([38]). In any adhesive category, pushout complements of monos (if they exist) are unique up to isomorphism.
The significance of this lemma is that it establishes the uniqueness of DPO rewriting in adhesive categories. As already mentioned, a DPO rewrite consists of two operations -first, the pushout complement is computed and then the pushout of the newly established span. The pushout is always unique and the above lemma tells us that the entire DPO rewrite is then unique as well.
The next lemma will be useful in showing that all morphisms in our DPO diagrams are mono. Proof. In any adhesive category, monomorphisms are stable under pushout (Lemma 2.1.10).
Therefore, s is a monomorphism.
The square commutes and therefore we know m • l = s • k. Both m and l are monomorphisms and therefore m • l and thus s • k are also monos. The latter then implies k is a mono as well.
Adhesive categories ensure that pushout complements are unique, but we still don't know under what conditions a pushout complement exists. However, the answer is not provided by the framework of adhesive categories. Instead, the conditions need to be determined in every model category in which we wish to do rewriting separately.
The following definition formalizes this idea. The matching conditions are also called the gluing conditions in the literature.
Note, that in the above definition a matching has to be a monomorphism. In the literature, this is not always the case, but in this thesis we will only consider injective matchings, so we build this requirement into the definition in order to simplify the rest of the presentation.
The matching conditions depend on the category C in which we wish to compute the pushout complement. For example, the matching conditions in the category Set are trivial -they are satisfied by any mono. The matching conditions in the category MultiGraph are given below.
Example 2.1.15 ([11]). In the category MultiGraph, given a rewrite rule L l ← − I r − → R and a monomorphism m : L → H, the pushout complement of (l, m) exists iff the following condition is satisfied: The matching conditions for graphs have been well-known for decades and clearly they are easy to decide by a computer. We shall see that when we consider rewriting edNCE grammars, the matching conditions will be straightforward generalisations of the above matching conditions for graphs.
The final and most central notion that we will introduce in this section is that of a DPO rewrite. We will also refer to DPO rewrites simply as rewrites because this will be the only kind of rewriting that we will consider. A rewrite consists of applying a rewrite rule at a specified mono to a given object. Then, a pushout complement (left square) is computed (if it exists) which may or may not be unique. In an adhesive category, we already know that it is unique. Following that, the second pushout (right square) is computed which may or may not exist, however in an adhesive category it is guaranteed to exist. This can be made precise via the following theorem. Proof. m satisfies the matching conditions therefore a pushout complement of (l, m) exists. From Lemma 2.1.12 the pushout complement is unique (up to isomorphism) and from Lemma 2.1.13 it follows that k and s are mono. Then, by the first defining property of adhesive categories, the right pushout square exists and therefore M is uniquely determined (up to isomorphism). Finally, Lemma 2.1.10 shows that f and g are also mono.
Therefore, in any adhesive category, a rewrite rule and a matching ensure that a rewrite can be performed and it is unique. Next, we will consider two concrete examples of DPO rewriting in adhesive categories -one in the category of sets and one in the category of multigraphs.

Example: DPO rewriting in Set
As a concrete example, let's see how DPO rewriting works in the category of sets and total functions Set. In full generality, in Set, the pushout of the two monos l, k in the square below: In Set, the matching conditions are trivial -they are always satisfied by any monomorphism. Therefore, this rewrite rule can be applied to any set with cardinality three or higher. What the rule does is to preserve two elements of the target set (a, b), delete one other element (c) and then add two additional elements to it (f, g). An application of the rule to the target set {a, b, c, d, e} is shown below: where again the morphisms are the subset inclusions. Computing the pushout complement can be done by removing the interior elements from the target set. In this case, this amounts to removing the element c. Once that is done, the right pushout is computed, which in this case is just the union of the two sets.
Of course, the morphisms do not have to be subset inclusions because DPO rewriting is defined up to isomorphism. So, let's consider another case -we will apply the same rewrite rule to the target set {a , b , c , f, g}. The result is illustrated by the following DPO diagram: where the horizontal morphisms are subset inclusions and the vertical morphisms all In the rest of the thesis, we will be doing DPO rewriting on graphs and edNCE grammars. As we have already pointed out, DPO rewriting on edNCE grammars is a straightforward generalisation from DPO rewriting on graphs. The latter is, in turn, a generalisation of DPO rewriting on sets. Indeed, sets can be seen as totally disconnected graphs (graphs with no edges) and vice versa. In this sense DPO rewriting on graphs fully generalises DPO rewriting on sets. Nevertheless, DPO rewriting on sets acts in the same way as DPO rewriting does (component-wise) on the set of vertices and set of edges of a graph and also in the same way as DPO rewriting on the different components of edNCE grammars as we shall see. Therefore, understanding DPO rewriting on sets is crucial for the rest of the work as it is the most fundamental mechanism for rewrites.

Example: DPO rewriting in MultiGraph
Next, let's consider DPO rewriting in the category of multigraphs. In MultiGraph, the pushout and the pushout complement are computed component-wise in the same way as in Set. The pushout of the two monos g, k in the square below: is given by the multigraph H with components (vertices and edges) V H and E H given by the pushouts in Set : If we choose the matching which maps v i → v i from the different multigraphs, then where again all morphisms in the above diagram map v i → v i and the mapping of the edges is then uniquely determined. However, the matching conditions in MultiGraph are not trivial, as already pointed out. In the example above they are satisfied, so the above rewrite rule may be applied to the specified target multigraph and then the result is the multigraph in the bottom right corner of the diagram, which again is only defined up to isomorphism.
In Set we cannot provide an example where a mono may fail to produce a rewrite.
However, we can do so in MultiGraph. For example, consider the same rewrite rule, but this time let's take the target multigraph H given by: where the matching maps v i → v i . Then, consider the following diagram: The no dangling edges condition is violated, because the target multigraph has an edge outside of the image of m which is incident to an interior vertex (v 3 ). Therefore, there exists no multigraph K such that the above square is a pushout. To understand why, recognize that the offending edge must be in the image of s : K → H and therefore both vertices v 3 and v 4 must be in the image of s as well. However, then vertex v 3 in H must be in the images of both m and s while it has no pre-image in I and this clearly violates the pushout construction on vertices.
DPO rewriting on multigraphs, and in particular, string graphs, is how we formalize equational reasoning on string diagrams. String graphs represent string diagrams, rewrite rules on string graphs represent rewrite rules between string diagrams and a DPO rewrite on a string graph represents a string diagram rewrite. By making use of (partially) adhesive categories, these concepts can be generalised from graphs to edNCE grammars and in this way we may model equational reasoning on entire families of string diagrams and not just concrete diagrams.

Partially Adhesive Categories
In this section we will describe Partially Adhesive Categories. They were first introduced by Kissinger and Duncan in [17] and later in [31] where they were slightly modified. Intuitively, a partially adhesive category C is a category which embeds fully and faithfully into an adhesive category D, such that DPO rewriting in C behaves in the same way as it does in D, provided that certain additional conditions are satisfied.
As we have seen in the previous section, multigraphs form an adhesive category.
However, graphs, which are simply multigraphs without parallel edges or self-loops, do not form an adhesive category, but a partially adhesive one. Of course, DPO rewriting in the category of graphs behaves in exactly the same way as it does in the category of multigraphs, provided that we avoid pushouts which may establish parallel edges. This example is discussed in detail in Subsection 2.2.1.
In an adhesive category, pushouts always exist over a span of monomorphisms.
However, in partially adhesive categories, this may not necessarily be the case. Instead, pushouts over monomorphisms may exist provided that the span satisfies further requirements. Similarly, the matching conditions in a partially adhesive category may be stricter compared to the matching conditions in the ambient category.
In the main chapters of this thesis, we will mostly be performing DPO rewriting on categories which are not adhesive, but partially adhesive. In particular, the graph model assumed by edNCE grammars does not form an adhesive category, but a partially adhesive one. Moreover, edNCE grammars, which can be seen as a generalisation of these graphs, also form a partially adhesive category and not an adhesive one. Thus, partially adhesive categories provide us with a nice framework where we can describe how DPO rewriting works and how it relates to DPO rewriting in adhesive categories. Then, if we wish to use DPO rewriting in our model categories, all we have to do in addition is to identify the matching conditions and the conditions under which pushouts along monomorphisms exist. Moreover, under these conditions, DPO rewriting behaves in the same way as it does in the ambient adhesive category and we can therefore make use of the already established results related to adhesive categories.
We begin by introducing the formal definition for a partially adhesive category and afterwards we shall introduce the rest of the notions which are needed to understand rewrites within it. We will be following the presentation in [31]. So S-pushouts are exactly those pushouts in C which are preserved by S. When doing DPO rewriting in partially adhesive categories, we will limit ourselves to only these kinds of spans and pushouts. We shall see that the specific partially adhesive categories we are interested in (those of graphs and edNCE grammars) have simple and easily decidable conditions which characterise their S-spans (and therefore Spushouts) and the rest of the S-diagrams which we will introduce in this section. Definition 2.2.4 (S-pushout complement [31]). An S-pushout complement for a pair of arrows (l, m) in C is a pushout complement, where the following diagram is an S-pushout: Similar in spirit to the previous definition, S-pushout complements are those pushout complements which are preserved by S. Pushout complements in C are not necessarily unique, but if we restrict ourselves to S-pushout complements, then they are unique as the next lemma tells us. and moreover both squares are a pushout complement for the pair of morphisms (S(l), S(m)). S preserves monos and therefore, by Lemma 2.1.12 there exists an isomorphism i : S(K) → S(K ) making the following diagram commute: S is full and therefore, there exists an isomorphism i : K → K such that S(i ) = i. Then, by making use of the fact that S is also faithful, we get that the following diagram commutes: This lemma illustrates nicely how we may use important properties of adhesive categories when we suitably restrict the spans and the matchings in our partially adhesive category. The additional restrictions which may need to be imposed on the matching morphisms are formalised (but not specified) in the next definition. we say that M is the S-rewrite of t at m. We will use the same notation as the one for a (DPO) rewrite and write this as H t,m M and it will be clear from context which kind of rewrite we are referring to.
Clearly, every S-rewrite in a partially adhesive category is also a rewrite, but not vice versa. In this thesis, we are only interested in S-rewrites, because they behave in the same way as they do in their ambient adhesive category and we can therefore make use of the established results. This is made precise by the next theorem. Therefore, by restricting ourselves to S-rewrites in a partially adhesive category, many of the useful properties of adhesive categories may be reflected into the partially adhesive one. For example, because S is fully faithful, it will reflect all colimits and therefore pushouts in particular. In this thesis, the most important feature which gets reflected is the uniqueness of the pushout complement. However, the framework of partially adhesive categories may be useful in determining whether other important properties of adhesive categories also carry over, such as the Local Church-Rosser Theorem and the Concurrency Theorem, for suitable S-diagrams. We will leave this question open for future work.

Example: DPO rewriting in Graph
Now, let's consider a concrete example of a partially adhesive category. We already know that MultiGraph is adhesive, however if we restrict ourselves to graphs without self-loops or parallel edges with the same label, then we get a category which is not adhesive, but partially adhesive. These will be the kinds of graphs which we will be using throughout most of the thesis, so we will simply call them graphs for brevity and in order to distinguish them from multigraphs. They may be defined in a more compact way compared to multigraphs.
Definition 2.2.9 (Graph [24]). A graph over an alphabet of vertex labels Σ and an alphabet of edge labels Γ is a tuple H = (V, E, λ), where V is a finite set of nodes, is the set of edges and λ : V → Σ is the vertex labelling function.
This is the notion of graph that we will be using when working with contextfree graph grammars. This definition is more compact compared to the definition of multigraphs, because edges are uniquely identified by their source vertex, target vertex and edge label, so the entire edge data may be described as a subset of V × Γ × V .
Multigraphs are strictly more general and this is clearly impossible to do for them.
The requirement that our graphs do not have self-loops or parallel edges with the same label is crucial for establishing some of the properties for edNCE grammars which we will be using in later chapters.
Next, we define the category of graphs and graph homomorphisms and show that it is partially adhesive, where its ambient adhesive category is MultiGraph.
Definition 2.2.10 (Graph homomorphism). Given two graphs H, K over vertex and edge label alphabets Σ and Γ respectively, a graph homomorphism from H to K is a Definition 2.2.11 (Category of Graphs). Given a vertex label alphabet Σ and an edge label alphabet Γ, then we will denote with Graph Σ,Γ the category of graphs and graph homomorphisms over Σ and Γ. If the labelling alphabets are clear from the context, then we will simply refer to it as Graph.
Theorem 2.2.12. Graph is a partially adhesive category with embedding functor Proof. The definition of S and the theorem follow as a special case of Theorem 5.1.11.
However, while MultiGraph is adhesive, Graph is not. The reason is because Graph does not have unique pushouts complements over monos, which violates Lemma 2.1.12. In particular, consider the following two squares: where the morphisms are just subgraph inclusions. The left square is an S-pushout in Graph and therefore it is a pushout in both Graph and MultiGraph. However, the right square is not a pushout in MultiGraph, but it is a pushout in Graph. Therefore, the pair of morphisms (m, id) has two non-isomorphic pushout complements in Graph and thus, the category is not adhesive. For completeness, the pushout of the right span in MultiGraph is given by: that is, it establishes a pair of parallel edges (with the same label), which is not allowed in Graph. Therefore, S-rewrites in Graph are well-defined, however, general rewrites are not because pushout complements and thus rewrites are not necessarily unique.
Next, we characterise the S-spans (and therefore the S-pushouts).
Graph is an S-span iff the following condition holds: ParEdges: For any vertices v, w ∈ I, if there exists an edge (k(v), α, k(w)) ∈ K and an edge (r(v), α, r(w)) ∈ R, then there exists an edge (v, α, w) ∈ I.
Proof. This is a special case of Lemma 5.1.14 from the original body of work.
The main idea is that the above condition ensures that a span of monos cannot produce a pushout in MultiGraph which contains a pair of parallel edges with the same label. We proceed by characterising S-matchings (and therefore S-pushout complements). Proof. Again, this is a special case of Lemma 5.1.15 from the original body of work.
So, this lemma tells us that in order to construct an S-pushout complement, we simply have to follow the same procedure as in MultiGraph. Finally, the next theorem consolidates all of the requirements for doing S-rewrites. Edges: For any two vertices v, w ∈ I, if there exist edges (m • l(v), α, m • l(w)) ∈ H and (r(v), α, r(w)) ∈ R, then there must be an edge (l(v), α, l(w)) ∈ L.
Proof. Again, special case of Theorem 5.1.16 from the main body of work.
In summary, if we wish to perform DPO rewriting on graphs, such that it acts in the same way as it does on multigraphs, then we simply have to verify that the Edges condition is satisfied (in addition to the matching conditions). Therefore, all the examples presented in subsection 2.1.2 also hold in Graph as they do not violate the Edges condition.
DPO rewriting on graphs is just a special case of doing DPO rewriting on edNCE grammars. The reason that edNCE grammars form a partially adhesive category and not an adhesive one is precisely because their underlying graph model are graphs and not multigraphs. If we define edNCE grammars using multigraphs as the underlying graph model, then edNCE grammars form an adhesive category. From the perspective of DPO rewriting this is preferable, however this also has a negative effect on the language-theoretic properties of edNCE grammars and for this reason we will use the standard definition of edNCE grammars, which forms a partially adhesive category.

String Diagrams and String Graphs
In this section we begin by providing a short introduction to the theory of string diagrams and how they relate to (traced symmetric) monoidal categories. This is described in Subsection 2.3.1. Next, in Subsection 2.3.2 we describe string graphs, which are a discrete representation of string diagrams amenable to automation in software.

String Diagrams
String Diagrams were introduced by Roger Penrose in [43] as a way to conveniently represent Abstract Tensor Systems. A string diagram consists of a collection of labelled nodes which are drawn in a plane. Every node has a certain number of inputs and outputs which are drawn as wires. Nodes can be connected to each other (and even themselves) by connecting their inputs and outputs. A single node with its inputs and outputs represents an abstract tensor in Penrose's paper. Also, more generally, nodes can be used to represent arrows in monoidal categories [29]. A string diagram consisting of several nodes that are connected in some way represents tensor contraction in Penrose's paper and more generally, composition of morphisms in a monoidal category. It is possible for a string diagram to contain wires that are not connected to a node at some end and also wires that form circles. The length and shape of the wires is irrelevant -two string diagrams are equal if they are isotropic, that is, one diagram can be obtained from the other via a continuous deformation. An example of two isotropic string diagrams is provided below: The introduction of string diagrams by Penrose was limited to their applications for abstract tensor systems. The first more general treatment of string diagrams was pro-vided by Andre Joyal and Ross Street in the middle of the 1980s. Perhaps the most seminal paper related to string diagrams is [29] where the same authors show that reasoning with string diagrams is sound and complete for (traced symmetric) monoidal categories. In particular, if an equality between two morphisms in some monoidal category follows from the axioms of a monoidal category, then the string diagram representations of both morphisms are isotropic. As a result, equational reasoning with string diagrams provides shorter proofs compared to the standard term-based approach used in monoidal category theory, because the canonical morphisms get absorbed in the graphical notation and may be ignored.
For example, in any monoidal category C, the interchange law: is provable from the axioms of a monoidal category: However, using string diagrams, the interchange law is trivial: because both sides of the equation are represented using the same (isotropic) string diagram. Thus, reasoning for monoidal categories using string diagrams can be done modulo the interchange law, and in general, modulo any equation which follows from the axioms of monoidal categories. In this way, we can produce shorter equational proofs compared to the traditional term-based rewriting approach.
A single morphism f : A 1 ⊗ · · · ⊗ A n → B 1 ⊗ · · · ⊗ B m is represented as a string diagram: where the open-ended wires on the bottom are its inputs and the open-ended wires on the top are its outputs. The tensor product of f and g is represented by horizontal composition of diagrams: and the composition g • f is represented by plugging the outputs of f into the inputs of g (provided the two morphisms can be composed): As a specific example, let's consider monoids. In a monoidal category (C, ⊗, I), a monoid is a triple (A, m, e), where: Instead of reasoning about monoids in the usual notation using terms, we may use string diagrams to do so. In particular, setting: A A A m := e := A then the monoid axioms become: Equational reasoning for string diagrams is performed via subdiagram substitution.
As an example, given the following string diagram: we can apply one of the unitality axioms by matching one side of the axiom into the diagram, cutting it out along the input/output wires of the subdiagram and then replacing it with the other side of the unitality axiom (the replaced subdiagram is indicated by the dashed box): In general, by using string diagrams in this way, we can reason equationally about (traced symmetric) monoidal categories without having to perform any rewrite steps which follow from the monoidal structure of the category.
However, Joyal and Street describe string diagrams in terms of non-discrete topological notions. One of our primary interests related to string diagrams is the ability to perform computer-assisted proofs using them. The formalisation provided by Joyal and Street is difficult to implement in a theorem prover and for this reason we will consider a discrete representation of string diagrams which makes use of graphs. This representation is called String Graphs and it is introduced in the next subsection.

String Graphs
String Graphs were originally introduced under the name "Open Graphs" in [15], [16]. Since then, the theory has been further developed and the term was changed to "String Graphs" in [31]. String graphs were introduced in order to represent string diagrams in a way that allows for efficient automation by computer systems.
String graphs are a special kind of labelled directed graphs. Every vertex of a string graph is either a wire-vertex or a node-vertex. Constructing a string graph from a string diagram (and vice versa) is straightforward -for every node in the diagram we create a node-vertex and we replace the wires with a sequence of wire-vertices which are connected by edges. Node-vertices should be thought of as the main vertices of the graph, whereas wire-vertices are only there to assist in the formalization of string diagrams as actual graphs. Wires which are not connected at some end to a node, must end in a wire-vertex in the string graph. The notion that two string diagrams are equal under topological changes translates to wire-homeomorphism in string graphs -two string graphs are equal if we can get one from the other by increasing and decreasing the number of wire-vertices on certain wires. As an example, the following two string graphs are equal and represent the string diagrams from Equation (2.3.1): We now proceed to give formal definitions for all notions related to string graphs as they will be the fundamental objects in which we are interested in. Recall that so far we have introduced two different graph models -multigraphs (cf. Definition 2.1.7) and graphs (cf. Definition 2.2.9). In this section we will define string graphs assuming the multigraph model, because this is how they have been originally introduced and because we wish to stay close to the background theory. In addition, the multigraph model allows us to define self-loops on wire-vertices, whereas the other model does not. This is discussed at the end of the section where we explain why string graphs may be alternatively defined using graphs (in the sense of Definition 2.2.9) without losing any expressivity for practical purposes.
We begin by introducing the labelling alphabets which we shall use.
Definition 2.3.1 (String Graph Alphabets). Throughout this section and the rest of the thesis, we will be working with edge and vertex labelled graphs. There are finitely many labels which are split into several different alphabets. This is made precise by the following definition: 1. ∆ is the alphabet of vertex labels.
2. N ⊆ ∆ is the alphabet of node-vertex labels and W = ∆ − N is the alphabet of wire-vertex labels.
3. Γ is the alphabet of all edge labels.
Thus, each vertex label is either a node-vertex label or a wire-vertex label. With this in place, we may now define string graphs.
Definition 2.3.2 (String Graph [33]). A string graph over an alphabet of vertex labels ∆ and an alphabet of edge labels Γ is a directed labelled multigraph whose vertices are labelled by the set ∆ and whose edges are labelled by the set Γ, where vertices with labels in N are called node-vertices and vertices with labels in W are called wire-vertices, and the following conditions hold: 1. there are no edges directly connecting two node-vertices 2. the in-degree of every wire-vertex is at most one and 3. the out-degree of every wire-vertex is at most one The category of string graphs over ∆ and Γ is denoted by SGraph ∆,Γ and it is the full subcategory of MultiGraph ∆,Γ whose objects are string graphs. When ∆ and Γ are clear from the context, we will simply write SGraph.
The above definition talks about directed string graphs, but we can easily modify it in order to define undirected string graphs. All of our proofs, propositions and definitions in this thesis will be about directed graphs, but they can easily be modified to cover undirected graphs as well. However, for brevity, we will only stick to the directed case, which is also more complicated. Still, we shall sometimes provide examples involving undirected graphs (and graph grammars) because they may be simpler to illustrate certain ideas.
We depict string graphs in the following way. Node-vertices and edges are depicted in the same way we depicted vertices and edges for graphs. Wire-vertices will be depicted using black nodes which are smaller compared to node-vertices. While we do allow wire-vertices to be labelled, we can usually ignore their labels as they usually do not carry semantic meaning. For this reason, we will often not depict the label of a wire-vertex.
3. An example of a string graph with three node-vertices is provided below: The category SGraph is not adhesive, because it does not have unique pushout complements. The reason is the same as for the category of graphs -parallel edges are not allowed. In fact, the same counter-example from Subsection 2.2.1 may be used to show that SGraph is not adhesive, where we use wire-vertices in particular.
However, SGraph is partially adhesive as shown by the next proposition. Proof. The inclusion functor is obviously full and faithful. Monomorphisms in SGraph are just injective graph homomorphisms and therefore they are preserved by I.
String diagrams may have inputs and outputs which can be used to compose string diagrams between each other. The same notion also exists for string graphs and is defined next. 1. for all v ∈ In I at least one of k(v) and r(v) is an input 2. for all v ∈ Out I at least one of k(v) and r(v) is an output When working with string graphs, we shall restrict ourselves to special kinds of rewrite rules which allow us to correctly simulate string diagram rewriting. They are presented in the next definition.  The pushout complement in MultiGraph is the full subgraph K ⊆ H whose components are given by X H − m(X L − l(X I )), where X ∈ {V, E}, as shown in Subsection 2.1.2. Thus, to complete the proof, we have to show that K is a string graph.
H is a string graph and K is obtained from H by removing some edges and vertices. This cannot violate any of the three conditions from Definition 2.3.2 and therefore K must be a string graph. v ∈ I, then r(v) is an input in R or k(v) is an input in K (the case for outputs follows by the same arguments). Assume the opposite, that is, neither k(v), nor r(v) is an input. Because r(v) is not an input, this means that r(v) must be an output in R, according to the definition of string graph rewrite rule. Again from the same definition, it follows l(v) must be an output and moreover l(v) has in-degree exactly one, because isolated wire-vertices are not allowed in L. Now, observe that the incident edge of l(v) in L will be removed when computing the pushout complement K. Thus, k(v) is an input in K and we get a contradiction.
This theorem shows that DPO rewriting for string graphs is well-defined and behaves exactly as it does for multigraphs as long as we restrict ourselves to string graph rewrite rules. However, this alone is not enough to represent string diagrammatic rewriting. The last piece which is missing is the notion of wire-homeomorphism. We will first define wires and then we shall define what we mean by wire-homeomorphism. Definition 2.3.10 (Wire [33]). A wire is a maximal connected subgraph of a string graph consisting of only wire-vertices and at least one edge. There are three cases: (a) it forms a simple directed cycle, which is called a circle, (b) it is a chain where one or both endpoints are connected to node-vertices, which is called an attached wire, or (c) it is a chain not connected to any node-vertices, which is called a bare wire. ∼ and the left one is the minimal representative of its wire-homeomorphism class.
The main result regarding string graphs in [31] is that the category of framed cospans of string graphs modulo wire-homeomorphism is the same as the free traced symmetric monoidal category. This justifies the fact that DPO rewriting on string graphs modulo wire-homeomorphism correctly represents string diagram rewriting.
To understand why DPO rewriting without wire-homeomorphism is not sufficient to represent string diagram rewriting, consider the next example. So, in order to correctly represent string diagram rewriting using DPO rewriting on string graphs, we have to consider two string graphs to be equal when they are wire-homeomorphic. In particular, when matching a string graph L onto another string graph H, then we might have to grow or shrink some wires in H, before we can perform a rewrite. The next two definitions make this precise.  involving the string graph L as the LHS of some string graph rewrite rule. Note, that in this case a non-injective matching would also succeed, however, the theory of string graphs and its correctness has only been described over injective matchings.
For an alternative representation of string diagrams where this is not necessary, see Section 2.6.
Before we conclude this section, we point out that we can alternatively define string graphs using Definition 2.2.9 instead of using multigraphs. However, there is a small caveat. Observe, that any string graph may not have parallel edges -there can be no edges between a pair of node-vertices and the in-degree (out-degree) of any wire-vertex is at most one. Node-vertices cannot have self-loops, but a wire-vertex may have a self-loop, like in the following example: However, any string graph which contains a self-loop is wire-homeomorphic to a string graph which contains no self-loops and is therefore a graph in the sense of Definition 2.2.9. This can be done by simply removing any wire-vertex with a selfloop and introducing a circle wire: String Graph rewriting is performed modulo wire-homeomorphism, so this limitation of the graph model is insignificant. When working with graph grammars, we will be using this notion of graphs and string graphs. This is because edNCE graph grammars do not allow for self-loops and therefore we need to consider string graphs, not as multigraphs, but as graphs in the sense of Definition 2.2.9.

Families of String Diagrams and !-graphs
In this section we will introduce how to rewrite not just singular string diagrams, but entire sets, or families, of string diagrams. This is described in Subsection 2.4.1. Next, in Subsection 2.4.2, we describe how we can formally and finitely represent certain families of string diagrams using a generalisation of string graphs, called !-graphs.

Infinite families of string diagrams
In the previous section we explained how string diagrams can be used to represent morphisms in monoidal categories. In particular, a single string diagram represents a single morphism and by rewriting a string diagram we establish an equality between two morphisms from the category. However, this process can be limiting, as it does not immediately extend to infinite sets of morphisms, which is necessary for some practical applications. For example, (quantum) protocols and algorithms are usually described in terms which allow for input of arbitrary size and therefore a complete description in terms of string diagrams requires the ability to express infinite families (or sets) of string diagrams.
Let's consider a simple example of an algebraic structure where the ability to reason about infinite families of morphisms can be beneficial. We saw how we can represent monoids using string diagrams in the previous section. We also showed how equational reasoning can be done for concrete morphisms. Using simple inductive arguments we can prove propositions which establish infinitely many equalities between pairs of morphisms which are related in a certain way.
For example by using associativity of the monoid operation, we can prove that for any n ∈ N, n ≥ 2, an n-ary left-associative application of the monoid operation m is equal to an n-ary right-associative application of m. Using terms this can be expressed as: Using string diagrams, the same proposition can be expressed more elegantly: In both cases, we use the familiar (· · · ) notation in order to indicate that we are representing an infinite family of morphisms. In this way, we establish an equational schema, which represents infinitely many equalities between pairs of morphisms -for every specific choice of n, we know that an n-ary left-associative application of m is equal to an n-ary right-associative application of m. For example, if n = 2, then we simply get the associativity axiom. If n = 3, we get: The usefulness of this sort of reasoning should be clear -once we have established an equational schema between two families of morphisms then we can easily establish equalities between concrete morphisms by choosing appropriate instantiations (in this case, choosing the same number of applications on both sides). Our primary motivation is to design a mathematical framework which supports equational reasoning for infinite families of string diagrams in a formal way which can be automated in software tools. We have already seen that we can use string graphs as a discrete representation of string diagrams. However, the intuitive (· · · ) notation is not precise enough for direct implementation in software. Towards this end, we will provide a short introduction to the theory of !-graphs which allows us to formally represent and do equational reasoning about certain infinite classes of string graphs.

!-graphs
!-graphs (pronounced bang graphs) were introduced in [30] under the name pattern graphs and were later renamed to their current name in [40] which contains the most complete and detailed description of !-graphs. A !-graph is a generalised string graph which allows us to represent infinite families of string graphs in a formal way. In addition to wire and node vertices, !-graphs also have specially marked subgraphs called !-boxes. These subgraphs may be copied infinitely many times (while preserving connection relations), thus allowing us to represent an infinite set of string graphs in a finite way.
The motivation behind !-graphs is to remove some of the informalities in expressing infinite families of rewrite rules and infinite families of graphs using the (· · · ) notation in order to ease the development of software proof-assistants.
In this subsection, we will provide a short introduction to the theory of !-graphs which will allow the reader to follow the rest of the presentation. We will first define !-graphs as special kinds of graphs in Subsection 2.4.2.1, then in Subsection 2.4.2.2 we will show how !-graphs induce infinite languages of string graphs.

Graph-theoretic notions of !-graphs
We start by describing the labelling alphabets which we shall use.
Definition 2.4.1 (!-Graph Alphabets). We will use the following labelling alphabets when working with !-graphs.
1. Σ is the alphabet of vertex labels.
2. N ⊆ Σ is the alphabet of node-vertex labels 3. W ⊆ Σ is the alphabet of wire-vertex labels.
where ! is a special label which we will use to label !-vertices.

Γ is the alphabet of all edge labels.
For the rest of the section, all of our constructions will be over an arbitrary !graph alphabet as described in the previous definition. Any vertex with label "!" will be called a !-vertex. For a multigraph G, the full subgraph of G consisting only of !-vertices will be denoted as β(G).
So, !-graphs use the same labelling symbols as string graphs, except for the newly introduced label "!", which marks !-vertices. We will depict !-graphs in the same way as string graphs, with the exception that !-vertices will be coloured in blue and will have a small square shape. In addition, edges incident to !-vertices will also be coloured in blue. In !-graphs, the full subgraph consisting of only !-vertices must form a partial order, or more precisely, it must form a posetal graph.
Definition 2.4.5 (Posetal multigraph [40]). A multigraph is called posetal, if it contains at most one edge between any two vertices and, when considered as a relation, forms a partial order.
Example 2.4.6. The following graph is posetal: The next definition is useful as just a simple notational convenience.
Definition 2.4.7 (Forgetful mapping [40]). For every multigraph G, we define U (G) to be the graph G − β(G), that is, the full subgraph of G which contains no !-vertices.
So, if G is the graph from Example 2.4.2 and H is the graph from Example 2.4.4, then U (G) = H. !-graphs can be seen as generalised string graphs and then the mapping U can be seen as a forgetful functor from the category of !-graphs to the category of string graphs. This should become clear after we formally define !-graphs.
!-graphs represent infinite families of string graphs by allowing certain subgraphs to be copied infinitely many times. For a given !-graph, the specific subgraphs which may be copied in such a way are given by its !-boxes, which are introduced next. The next definition introduces !-graphs, which are the main objects of study in this section.
2. U (G) is a string graph.
is an open subgraph of U (G).

For any two !-vertices
Remark 2.4.10. The above definition is equivalent to the one presented in [40], where all node-vertex types are allowed to have arbitrary arity. In particular, the first condition is not explicitly stated there, but it follows from the slice construction which the author uses.
Condition 1 from the definition above implies that there are no out-edges from wire-vertices or node-vertices to !-vertices. Condition 2 then justifies the fact that !-graphs can be seen as generalised string graphs. Condition 3 imposes a partial order on the !-vertices. Condition 5 then requires that a !-box B(b ) must be entirely contained in any other !-box B(b) where b is greater than b with respect to the partial order. Finally, condition 4 implies that copying a !-box any number of times, while preserving the connection relations with the rest of the graph, would result in a valid !-graph. The definition of a !-graph suggests a more compact graphical presentation which we will be using from now on. We will depict the !-vertices as before, but instead of explicitly depicting the outgoing edges of a !-vertex b, we will simply draw a blue box around all of the vertices which are its successors. Thus the insides of such a blue box is simply the !-box B(b). The !-vertex itself will be depicted as one of the corners of the blue box. Given a !-graph G with !-vertex b, we can produce new !-graphs from G by applying one of two operations (any number of times) to b. They are described in the next definition.
Definition 2.4.13 (!-box Operations). Given a !-graph G and a !-vertex b, the two !-box operations are defined as follows: • EXPAND b (G) is defined by the pushout of the following subgraph inclusions: Theorem 2.4.14. Let G be a !-graph and b ∈ G be a !-vertex. Then, EXPAND b (G) and KILL b (G) are also !-graphs.
Proof. This follows from Theorem 4.3.4 of [40] after recognising that an EXPAND operation is simply a COPY operation followed by a DROP operation, as defined in that work.
From an operational point of view, applying a KILL operation to a !-box has the effect that the entire !-box is removed from the graph.
The second !-graph in that example has two different !-boxes and there are different ways we can apply a KILL operation: Applying an EXPAND operation to a !-box creates a copy of the !-graph in its contents and connects it to the rest of the graph in the same way as the original.
Example 2.4.16. Consider the !-graphs from Example 2.4.11. Applying an EX-PAND operation to the first one yields the following result: The second !-graph in that example has two different !-boxes and there are different ways we can apply an EXPAND operation: When working with !-graphs, we are always interested in the languages which they induce. Therefore, the following definition is crucial.
Therefore, the first !-graph represents the following family of string diagrams: whereas the second represents: In later chapters, we will compare !-graphs with context-free graph grammars and B-ESG grammars in terms of the expressiveness of their languages. In order to provide a more detailed picture, we will introduce two subclasses of !-graphs, which are characterised by the relationships between their !-boxes.

Example 2.4.21 ([35]). We illustrate the different kinds of relationships between
!-boxes using this example: b 1 and b 2 overlap trivially, because they only overlap on the interior of a wire connecting node-vertices in different !-boxes. b 3 and b 4 overlap non-trivially, because their intersection contains a node-vertex. b 5 and b 6 overlap non-trivially because their intersection consists of a wire-vertex which is not part of a wire whose endpoints are in distinct !-boxes. For any other pair of !-boxes, their intersection is empty and therefore they overlap trivially as well.
Also, there is no pair of nested !-boxes. In particular, observe that the contents of b 6 are just the wire-vertex and the !-vertex b 6 itself. However, b 6 ∈ B(b 5 ), because b 6 is depicted as being outside of the !-box B(b 5 ). It is easy to see that BGNO BGTO BG. Before we conclude this section, we point out a subtle, yet very important, difference in the operational semantics between nested and non-nested overlapping !-boxes. Consider the following two !graphs: The language of H 1 is given by: The language of H 2 is given by: That is, if we view these string graph languages as the string diagram languages they represent, then L(H 1 ) is the language of all trees of depth at most two, whereas is the language of all balanced trees of depth at most two. For every string graph H ∈ L(H 1 ), every node-vertex connected to the root via a wire has an arbitrary number of children. However, for every string graph H ∈ L(H 2 ), every two nodevertices connected to the root via a wire have the same number of children. This is because for every expansion of b 1 (b 2 ), a copy of the string graph in their intersection is produced which is added to the contents of b 2 (b 1 ): As a result, if one of the !-boxes is expanded n times and the other m times, then there would be nm copies of the string graph in their intersection.

Graph Grammars
Graph Grammars have been developed as a generalization of the well-known contextfree grammars for strings. A graph grammar can be thought of as a finite collection of productions which specify instructions on how to generate (infinite) sets of graphs.
In this section we will provide an introduction to the theory of context-free graph grammars. They can be split up into two main groups -Vertex Replacement (VR) [24] and Hyperedge Replacement (HR) [18]. The VR grammars represent the connecting approach to graph transformation, whereas the HR grammars represent the gluing approach to graph transformation.
The connecting approach is usually described in set-theoretic terms and the gluing approach is usually described in algebraic (or categorical) terms. In later chapters, we will model equational reasoning using DPO rewriting which is an example of the gluing approach. As we have seen, DPO rewrites may be understood categorically.
At first glance, this consideration makes HR grammars a more attractive candidate to represent families of string graphs. As we show in Chapter 3, HR grammars and VR grammars have the same expressive power on string graphs. However, we argue that this expressive power is insufficient and we need to introduce an extension in order to be able to represent important languages of string graphs. VR grammars are strictly more expressive on (unrestricted) graphs and there is a simple extension which allows them to represent the languages we are interested in. However, the author does not know how to extend HR grammars to serve the same purpose and for this reason we will be using VR grammars for the rest of the thesis.
We will follow the presentation in [24] as it is the standard and most comprehensive reference on VR grammars. In particular, we will be working with confluent edNCE grammars (C-edNCE), which are the largest class of deterministically confluent graph grammars.

edNCE grammars
Throughout this section and the rest of the thesis, we will be working with edge and vertex labelled graphs. There are finitely many labels which are split into several different alphabets. This is made precise by the following definition and we will use the same alphabets throughout this work unless otherwise noted.
Definition 2.5.1 (Alphabets). We will use the following alphabets: 1. Σ is the alphabet of all vertex labels.

∆ ⊆ Σ is the alphabet of terminal vertex labels.
3. N ⊆ ∆ is the alphabet of node-vertex labels and W = ∆ − N is the alphabet of wire-vertex labels.
4. Γ is the alphabet of all edge labels. 5. Ω ⊆ Γ is the alphabet of all final edge labels.
In most of this thesis, we will have Γ = Ω, so all edge labels will be final. However, we will always need nonterminal vertex labels for our grammars in order to perform derivations. In addition, because we will be working with string graphs, the terminal vertex labels are partitioned into two sets -node-vertices and wire-vertices. In this section this distinction between node-vertices and wire-vertices can be ignored, but this difference will be significant in later chapters when we start working with string graphs. edNCE graph grammars are not defined over multigraphs, but over graphs in the sense of Definition 2.2.9. So, this is the graph model which we are working with in this section. Next, we formally introduce the notion of a graph language.
Definition 2.5.2 (Graph Language [24]). The set of all graphs over Σ and Γ is denoted by GR Σ,Γ . The set of all graphs modulo graph isomorphism is denoted by So, a graph language is a potentially infinite set of graphs, where isomorphic graphs are identified together. The graph grammars that we are interested in will be generating graph languages. For simplicity, we shall simply refer to graph grammars as grammars and to graph languages as languages and it should be clear from the context when we are talking about graph languages or string languages generated by string grammars.
The next concept we introduce is an extension to our notion of graph. An extended graph provides the necessary information on how a specific graph can be used to replace a nonterminal vertex and connect it to the local neighbourhood of the nonterminal vertex that is to be replaced. [24]). An Extended Graph over Σ and Γ is a pair (H, C), where H ∈ GR Σ,Γ is a graph and C ⊆ Σ×Γ×Γ×V H ×{in, out}. C is called a connection relation and its elements (σ, β, γ, x, d) are called connection instructions.

Definition 2.5.3 (Extended Graph
The set of all extended graphs over Σ and Γ is denoted by EGR Σ,Γ .
Remark 2.5.4. In the literature, extended graphs are commonly referred to as graphs with embedding. However, in the next chapters we will be introducing the notion of grammar embedding which is defined in terms of extended graph embeddings. In order to avoid confusion between graphs with embedding and embeddings of graphs or embeddings of graphs with embeddings we have simply renamed the term. Other than this, the definition is the same as the one in [24].
The name for an extended graph is well-justified. If an extended graph has no connection instructions (i.e. C = ∅), then we can think of it as just an ordinary graph. Before we explain the significance of the connection instructions, we will first introduce a graphical notation for depicting extended graphs (and their connection instructions). The notation is essentially the same as in [24] but it only differs in some cosmetic details. The graph part is drawn as before. Around the graph, we will draw a rectangular box. A connection instruction (σ, β, γ, x, in) will be depicted in the following way: we place a σ-labelled vertex outside of the box; the label β is put next to an arc which we create from the σ-labelled vertex to the boundary of the box; γ is then placed next to another arc which goes from the endpoint of the previous edge to the vertex x of the graph. A connection instruction (σ, β, γ, x, out) is drawn in the same way, except that we reverse the direction of both arcs. {α, β, γ}. So, we have three kinds of edge labels, all of which are final. σ 1 -labelled vertices will be coloured in white, σ 2 -labelled vertices will be coloured in grey and σ 3 -labelled vertices will be coloured in black.
Then, the following extended graph (D, , } is depicted in the following way: However, when working with graph grammars, we are only interested in generating graphs (and graph languages) up to isomorphism, so the names of the vertices will often be irrelevant and we may omit them: We can think of an extended graph as just a normal graph with some additional information which describes how the graph should be substituted into another graph while replacing a nonterminal vertex. If we are given a mother graph (H, C H ) with a nonterminal vertex v ∈ H and a daughter graph (D, C D ), then if we replace the vertex v with (D, C D ), we get a new extended graph obtained in the following way. Every connection instruction (σ, β, γ, x, in) ∈ C D in the daughter graph means that for every σ-labelled vertex w in the mother graph for which there is a β-labelled edge going into the nonterminal vertex v of the mother graph, then the substitution process will establish a γ-labelled edge from w to x. This should become more clear after referring to example 2.5.8 which is presented in a graphical form as well. The meaning for (σ, β, γ, x, out) is analogous. Next, we provide a formal definition for the substitution operation, which is the fundamental mechanism underlying derivations in edNCE grammars.
Definition 2.5.6 (Graph Substitution [24]). Let (H, and is given by the extended graph whose components are: So, the substitution process may use the connection instructions in order to create new edges between the mother graph and the daughter graph. These new edges will be called bridges.
Definition 2.5.7 (Bridges [24]). The edges of (H, lished by the substitution process, i.e., that are not in E H or E D , are called bridges.
We will shortly introduce edNCE grammars, which perform derivations by substituting nonterminal vertices with extended graphs. Therefore, it is crucial to understand the substitution process and we will consider several examples.
Example 2.5.8. Let's use the same alphabets from Example 2.5.5 and the same extended graph (D, C D ). We will use this graph as a daughter graph, that is, we will be substituting it into a mother graph, which we will call (H, is not of the appropriate type. In the following several examples, the graph on the left is the mother graph and the graph on the right is the result of substituting in In the above example, we see that each connection instruction in C D is used to establish one new bridge, while the nonterminal vertex has only two incident edges.
In the above example, a single connection instruction is used to establish two bridges. In this example, we see that connection instructions in the mother graph may also be used to establish new connection instructions in the resulting graph in the same way that edges are used.
An important property of the substitution operation is that it is associative.
Associativity of graph substitution, together with confluence ensure that the derivations which we will be interested in may be adequately described using derivation trees in the usual sense.
Next, we define the concept of an edNCE Graph Grammar. edNCE is an abbreviation for Neighbourhood Controlled Embedding for directed graphs with dynamic edge relabelling. The justification for this name is the following: derivations in an edNCE grammar consist of performing graph substitution by replacing a nonterminal vertex with an extended graph as specified by some production of the grammar. As we have already seen, embedding an (extended) graph depends only on the neighbourhood of the nonterminal vertex which is being replaced, hence the NCE part of the abbreviation. Clearly, we are working with directed graphs (hence the d letter in the abbreviation). Finally, the e in the name stands for dynamic edge relabelling which means that edges connected to a nonterminal vertex may get their labels changed after the vertex is replaced with another graph.
Definition 2.5.10 (edNCE Graph Grammar [24]). An edNCE Graph Grammar is a tuple G = (Σ, ∆, Γ, Ω, P, S), where • Σ is the alphabet of vertex labels • ∆ ⊆ Σ is the alphabet of terminal vertex labels • Γ is the alphabet of edge labels • Ω ⊆ Γ is the alphabet of final edge labels • P is a finite set of productions Remark 2.5.11. We will always work with grammars where all edges are final. This does not result in a loss of expressive power. We shall also refer to rhs(p) as the body of the production and we shall refer to lhs(p) as the label of the production.
Instead of presenting grammars using set-theoretic notation, we will often present them graphically as it is more compact and intuitive. We will use the same notation as in [24]. A grammar is simply a set of productions with a designated starting nonterminal label. The graphical presentation simply depicts each production of the grammar. Productions are extended graphs, which we already know how to depict, together with a nonterminal production label. We depict a production by just drawing its associated extended graph and placing its production label at the top-left corner of the bounding frame.
Example 2.5.12. Let's consider an example edNCE grammar. The grammar below generates the set of all undirected complete graphs K n and will be referred to multiple times in this thesis. The edges and terminal vertices all have the same type and so we don't depict them for simplicity.
X S X X X The above grammar has three productions, given by where H 1 is the leftmost extended graph, H 2 is the middle extended graph and H 3 is the rightmost extended graph. This example is used to demonstrate the graphical depiction of edNCE grammars, but we will soon turn our attention to their languages.
Before we introduce the notion of derivation in an edNCE grammar, we first have to define production copies. In turn, they depend on the notion of extended graph homomorphism which we define next.
Definition 2.5.13 (Extended Graph homomorphism). Given two extended graphs Graph substitution is only defined for disjoint pairs of graphs. However, edNCE grammars have finitely many productions which specify what graphs need to be substituted in for nonterminal vertices. We are only interested in graph languages defined up to isomorphism and for this reason it is necessary to consider isomorphic copies of productions if we wish to have arbitrarily long derivation sequences.
Definition 2.5.14 (Production copy [24]). Two productions X 1 → (D 1 , C 1 ) and as an extended graph. For an edNCE grammar G = (Σ, ∆, Γ, Ω, P, S), we denote with copy(P ) the infinite set of all productions that are isomorphic to some production in P . An element of copy(P ) is called a production copy of G.
The next notion is crucial for understanding the operation of edNCE grammars. It formalizes which kinds of graph substitutions are legal for a given edNCE grammar.
Like their context-free string counterparts, derivations for graph grammars consist of a sequence of expanding nonterminals and replacing them with the body of an applicable production.
Definition 2.5.15 (Derivation [24]). For a graph grammar G = (Σ, ∆, Γ, Ω, P, S) and extended graphs H, H ∈ EGR Σ,Γ , let v ∈ V H be a vertex in H and p : X → (D, C) ∈ copy(P ) be a production copy of the grammar, such that H and D are disjoint. We If v and p are clear from the context, then we write H =⇒ H . A sequence of derivation steps Example 2.5.16. A derivation in the grammar from Example 2.5.12 for the complete graph on four vertices K 4 is given by: where the bridges are coloured in red.
Now that we have defined derivations of an edNCE grammar, we are ready to define its language. This is formalized by the next three definitions. For a given ed-NCE grammar, a starting graph is simply a graph with no connection instructions, no edges and just a single vertex labelled with the initial nonterminal label. A sentential form, similar to the context-free string case, is any graph (up to isomorphism) which can be derived from the starting graph. Finally, the language of a grammar consists of all terminal sentential forms modulo graph isomorphism.
Definition 2.5.17 (Starting Graph [24]). We say that sn(S, z) ∈ EGR Σ,Γ is a starting graph if it has only one vertex given by z, its label is S, the graph has no edges and no connection instructions.
Definition 2.5.18 (Sentential Form [24]). A sentential form of an edNCE grammar G = (Σ, ∆, Γ, Ω, P, S) is a graph H such that Sn(S, z) =⇒ * H for some z. We consider graph languages up to isomorphism. Therefore, in the definition above, for the starting graph sn(S, z), the choice of vertex name z does not matter.
Only the initial nonterminal label is relevant. Because of this, we will often refer to derivations in a grammar as S =⇒ * H.

Subclasses of edNCE grammars
The edNCE graph grammars as introduced so far are not necessarily confluent. The order of application of productions matters as it may produce different results. This makes reasoning about their derivations (and thus languages) considerably harder. Therefore, a natural subclass of edNCE grammars are those grammars which are confluent. Indeed, confluent edNCE grammars have nicer structural, decidability and complexity properties, their derivations may be described via derivation trees and there is also a powerful logical characterization of their languages. These grammars are called C-edNCE grammars, where the C stands for confluent. C-edNCE grammars are the largest class of deterministically context-free graph grammars which have been studied. For this reason, this class is also commonly known as VR (Vertex Replacement) graph grammars as it is the most general class of context-free graph grammars which utilise vertex replacement (as opposed to edge/hyperedge replacement).
The next definition formally introduces C-edNCE grammars by providing static conditions which guarantee confluence. The conditions are static in the sense that they can be easily checked (and decided) by examining the productions of a grammar. We provide the definition for completeness, but it is not crucial for understanding the rest of the thesis, because we will be working with specific subclasses of C-edNCE grammars which enjoy even nicer properties.
Definition 2.5.21 (C-edNCE grammar [24]). An edNCE grammar G = (Σ, ∆, Γ, Ω, P, S) is confluent or a C-edNCE grammar, if for all productions X 1 → (D 1 , C 1 ) and , and all edge labels α, δ ∈ Γ, the following equivalence holds: This static definition guarantees the following dynamic property which we shall refer to as dynamic confluence. In general, dynamic properties will describe some behaviour of the sentential forms of C-edNCE grammars while static properties will describe their productions in decidable terms. In this sense, the next proposition states that dynamic confluence is equivalent to static confluence for edNCE grammars and we can therefore decide if any edNCE grammar is confluent in both senses.
Proposition 2.5.22 (Confluence [24]). An edNCE grammar G = (Σ, ∆, Γ, Ω, P, S) is confluent iff the following holds for every graph C-edNCE grammars are confluent, however when performing derivations, the context around a nonterminal vertex may change. Because of this, C-edNCE grammars in general do not have a normal form called context-consistency which significantly simplifies multiple proofs and constructions in this work. For this reason, we will work with the largest subclass of C-edNCE grammars which are known to have this normal form (defined next) and we will leave the problem of determining whether our results hold for C-edNCE grammars in general for future work.

D does not contain edges between nonterminal vertices
2. C does not contain connection instructions of the form (σ, β, γ, x, d) where σ is a nonterminal label Therefore, in any B-edNCE grammar, the sentential forms are such that nonterminal vertices are never adjacent. It is easily seen that B-edNCE grammars satisfy the defining conditions for C-edNCE grammars, but not the other way around. Thus, they are confluent, but in terms of generative power they are strictly less expressive compared to C-edNCE grammars.
An interesting proper subclass of B-edNCE grammars are linear edNCE grammars.
Like their context-free string counterparts, they can have at most one nonterminal in the body of each production. As a result, their derivation trees are simply lines and their derivations are usually easy to understand.
Definition 2.5.24 (LIN-edNCE grammar [24]). An edNCE grammar G = (Σ, ∆, Γ, Ω, P, S) is linear, or a LIN-edNCE grammar, if for every production X → ( is nonterminal neighbourhood deterministic, or a Bnd-edNCE grammar, if, for every production X → (D, C), every nonterminal vertex x ∈ V D , all γ ∈ Γ and all σ ∈ ∆ : A proper subclass of Bnd-edNCE grammar are the apex grammars, where connection instructions are only allowed to terminal vertices. As a result, any vertex connected to a nonterminal will have its final neighbourhood determined after expanding each nonterminal it is connected to. These grammars can generate only languages of bounded degree.
If an apex grammar is also linear, then we shall call it a LIN-A-edNCE grammar.
These grammars are considered to form the simplest class of VR grammars in terms of structural and expressive properties. We will denote the class of languages which can be generated by an X-edNCE grammar by X-edNCE. Most constructions in this thesis will be built around B-edNCE grammars.

Derivation Trees
Like in the case for context-free string grammars, the order in which productions are applied in C-edNCE grammars does not matter. The result of two derivation sequences where some of the productions have been permuted will be the same graph. Thus, derivation trees for C-edNCE grammars are useful in the same way that derivation trees are useful for context-free string grammars -they provide a convenient representation which allows us to ignore the unimportant order of production applications and the trees also better capture the syntactic structure of the objects (graphs or strings) with respect to the grammar.
For the next two definitions we shall assume that the vertices in our edNCE grammars have a linear order. This order may be assigned to the vertices in an arbitrary way. It is only used in order to relate specific nonterminal vertices from the productions of our grammars to specific nodes in a derivation tree. We shall first provide the necessary definitions and then elaborate more on them and provide examples.
Definition 2.5.27 (p-labelled derivation tree). Let G be an edNCE grammar. A plabelled derivation tree of G is a rooted, ordered tree T of which the nodes are labelled by productions of G, such that if node u of T has label p, and rhs(p) has nonterminal vertices x 1 , ..., x k , in that order, then u has children v 1 , ..., v k , in that order, and the left-hand side of the label of v i in T equals the label of x i in rhs(p). is the label of the root of T , x 1 , ..., x k are the nonterminal vertices (in that order) in rhs(p) and T 1 , ..., T k are the direct subtrees of T (in that order), where in addition, we take isomorphic production copies such that the substitution is well-defined.
Remark 2.5.29. The above two definitions are essentially the same as the ones from [24]. However, the authors there define p-labelled derivation trees in terms of clabelled derivation trees. We will not be using c-labelled derivation trees and for this reason we provide the direct definition above which is equivalent to the one in [24].
From now on, we shall simply refer to p-labelled derivation trees as derivation trees.
From any derivation tree we can obtain a concrete derivation sequence and viceversa. Given a derivation tree, any tree traversal where each node of the tree is visited only after its parent had been visited first describes a concrete derivation sequence -the first production to be applied is the one identified by the root node and each following one is given by applying the production identified by the next node in the traversal where the nonterminal being replaced is the one identified by the connecting edge. In the other direction, given a concrete derivation sequence, a derivation tree can be constructed in a unique way -the root node of the tree is labelled with the name of the first production in the sequence, then the children of any node n in the tree are labelled by the productions of the sequence which expand the relevant nonterminal vertices in rhs(p), where the label of n is p.
Example 2.5.30. Consider the following A-edNCE (and thus B-edNCE) grammar which generates star graphs (complete bipartite graphs K 1,n ): where the names of the productions are shown on the left. Note, this grammar is not optimal and the same language can be generated by a LIN-edNCE grammar where the Y nonterminal vertices and productions are removed. However, this grammar is useful for illustrating derivation trees. Let's assume that the nonterminal vertices X have lower order than the nonterminal vertices Y in all productions of the grammar.
Thus, when expanding nonterminal vertices labelled X they will correspond to the left child in the derivation tree of a parent node. For example, consider the following derivation tree: The yield of this tree is the graph K 1,3 : which may be computed by performing any of the derivation sequences induced by the derivation tree. For example, a left-right depth-first traversal of this derivation tree yields the following derivation sequence: Because this grammar is confluent, then any other derivation sequence induced by this derivation tree will produce the same result, which is the yield of the derivation tree.
Note, that in general, the yield of a derivation tree for an edNCE grammar is not necessarily the same as the result of a derivation sequence induced by the tree.
This is because edNCE grammars in general are not confluent. However, we have restricted ourselves to confluent grammars only and because of that the order of production applications (and hence tree traversals) does not matter and they will always produce the same result.

Normal Forms
In this subsection we present several normal forms for B-edNCE grammars, all of which are well known in the literature. Our contribution is to point out that all of them can be combined into a single normal form. Working with normal forms with B-edNCE grammars allows for simpler reasoning and for more concise definitions which we will need later on in this thesis. For example, in Chapter 4, we provide necessary conditions on normal form B-edNCE grammars for certain properties. Stating all those conditions for arbitrary B-edNCE grammars would be much more challenging and certainly less elegant. However, the normal forms which we consider here do not restrict the expressive power of B-edNCE grammars, and moreover, they can all be constructed effectively by a computer.
Our first normal form is about nonfinal edges. In an edNCE grammar nonfinal edges are used in order to block subsequent derivations -once a nonfinal edge is established between a pair of terminal vertices, it cannot be modified any further and thus any subsequent sentential forms are not considered part of the language. This might sometimes help with grammar design, but it also makes grammars much more difficult to reason about, so we shall only consider grammars where nonfinal edges are not allowed at all. As the next lemma (and its corollary) show, this does not decrease our expressive power.
This was first proved in [48] for C-edNCE grammars. Another proof is presented in [24] where, in addition, the authors point out that the result also holds for B-edNCE grammars. Proof. After applying the construction in Theorem 2.5.32, simply declare all edge labels to be final. This has no effect on the generated language as all terminal sentential forms do not contain non-final edges.
Next, we introduce the context of a nonterminal vertex v. This information describes the label data of the neighbourhood of v. Definition 2.5.34 (Context [24]). For a vertex v of an extended graph H, we define the context of v in H by: The next normal form which we will introduce is about context consistent grammars. In a context consistent grammar, the context around every nonterminal vertex with a given label is always the same. This will be helpful for us in later chapters, because it will allows us to reason locally about the productions of grammars when showing some of the admissibility results that we need.
Definition 2.5.35 (Context consistent grammar [24]). We say that an edNCE grammar G is context consistent if there is a mapping η from Σ−∆ to the set of all possible contexts, such that for every nonterminal vertex v of every sentential form H of G, Thus, in a context consistent grammar, the context of a nonterminal vertex is determined by its label.
The next normal form which we will need is about neighbourhood preserving grammars. These grammars do not allow edges incident to nonterminals to be dropped during the embedding process. Any vertex incident to a nonterminal vertex in the mother graph will therefore be incident to at least one new vertex created by the daughter graph. This normal form will be useful in later chapters when we need to relate the inputs and outputs of a pair (or triple) of B-ESG grammars. In particular, it guarantees that any wire-vertex in any sentential form of such a grammar cannot subsequently become an input or output, if it wasn't one in the past.
Definition 2.5.36 (Neighbourhood preserving grammar [24]). We say that an ed-NCE grammar G is neighbourhood preserving if, for every sentential form H of G, every nonterminal vertex v of H, and every production p with lhs(p) = λ H (v), the Lemma 2.5.37 ([22]). For every B-edNCE grammar an equivalent B-edNCE grammar can be constructed which is both context consistent and neighbourhood preserving.
The next two normal forms have a direct analogy in the standard context-free grammars on strings. Any derivation step in a graph grammar (or string grammar) which contains no chain productions or empty productions will always add at least one terminal vertex (or terminal character) to its sentential forms. As a result, the number of terminal vertices (characters) in sentential forms always increases which makes it easy to decide some properties by using a bounding argument.
Definition 2.5.38 (Chain production [24]). Given an edNCE grammar, we say that a production X → (D, C) is a chain production, if D consists of a single nonterminal vertex.
Definition 2.5.39 (Empty production [24]). Given an edNCE grammar, we say that a production X → (D, C) is an empty production, if D is the empty graph.
In the literature, there's a well-known normal form for C-edNCE grammars where all empty productions can be removed (see [24]). Obviously, if the empty graph is part of the language of a grammar G, then we cannot obtain a normal form for G which contains no empty productions. For this reason, we will consider a normal form where all empty productions, except for possibly an initial one, are removed.
The next normal form also translates immediately into the standard string grammars. A reduced grammar is one where every production may be executed at least once in some derivation. That is, there exists no production which is not reachable from an initial one. Such unreachable productions have no effect on the generated language and may simply be ignored. This normal form will be useful for us when we characterise some necessary conditions for our grammars that ensure they generate only languages of string graphs. Definition 2.5.40 (Reduced grammar [24]). An edNCE grammar is called reduced if every production of the grammar participates in at least one concrete derivation.
In order to determine whether an edNCE grammar is reduced, we simply have to check if every production of the grammar is reachable from an initial production.
The final normal form which we introduce is about grammars which contain no useless connection instructions. As the name suggests, useless connection instructions can simply be removed from any edNCE grammar. Of course, this requires identifying those connection instructions first. It's not immediately obvious how this can be done for arbitrary B-edNCE grammars, but we shall see that this is easy under some of the conditions of the already mentioned normal forms. B-ESG grammars which contain no useless connection instructions are easier to reason about when it comes to relating inputs and outputs in B-ESG rewrite rules. Definition 2.5.41 (Useless connection instruction [24]). For a given edNCE grammar, we say that a connection instruction of some production is useless, if for all possible concrete derivations, the connection instruction is never used by the substitution process in order to establish a bridge.
The central theorem of this section simply states that all of the definitions concerning B-edNCE grammars provided here can be combined into one normal form. An equivalent grammar without empty productions or chain productions can be effectively constructed. For a proof, see [24]. The construction for removing empty productions is a straightforward generalisation to the one for context-free string grammars -in the productions of the grammar substitute the empty graph for some nonterminal vertices that can generate the empty graph and finally delete all empty productions, except for possibly an initial one. This doesn't violate any of the conditions 1-3, because the replaced nonterminal vertices must have empty context. The construction for removing chain productions is also analogous to the one for context-free string grammars -it consists of composing several productions of the original grammar into one and then adding that production to the grammar. This composition preserves properties 1-4.
Creating an equivalent grammar which is reduced simply involves removing all productions which are unreachable from an initial production. This doesn't have an effect on the generated language, because these productions can obviously never be used in any concrete derivation. Therefore conditions 1-6 can be combined.
Finally, it should be clear that we can remove useless connection instructions without changing the language of the grammar, because by definition they do not affect any derivation. Identifying the useless connection instructions for a grammar which satisfies conditions 2-3 is particularly easy -for a production X → (D, C) the useless Obviously, doing this doesn't violate any of the previously established properties 1-6, which completes the proof.
We will be using this normal form for several proofs, so we give it a name.

Monadic Second Order Logic for C-edNCE grammars
Monadic Second Order (MSO) logic provides a useful and convenient language for describing graphs and graph properties. C-edNCE languages are fully characterised by MSOL in a grammar-independent way. In particular, the class of C-edNCE languages is the class of languages obtained by applying a MSO definable function to the set of all trees over a ranked alphabet. These results have proven to be very useful and they have led to several important decidability and closure results.
We will provide a brief introduction to MSO logic and state some properties which are relevant for C-edNCE grammars. For our purposes, only a few of the relevant notions are required in order to be able to understand the proofs in the rest of the chapters. The presentation of MSO logic presented below follows that of [24].
For fixed alphabets Σ and Γ of vertex labels and edge labels respectively, we will define the (infinite) language of MSO formulas and denote it with MSOL(Σ, Γ). MSO formulas have two types of variables. The first type are vertex variables, which we will denote with lower Latin letters such as u, v, w, etc. For a given graph H ∈ GR Σ,Γ , the vertex variables will range over the vertices V H of H. The second type of variables are vertex-set variables, which we will denote with capital Latin letters, such as U, V, W, etc. For a given graph H ∈ GR Σ,Γ , the vertex-set variables will range over subsets of V H . Edge variables or edge-set variables are not allowed. Each MSOL formula expresses some property of a graph H ∈ GR Σ,Γ .
There are four different types of atomic formulas in MSOL, where the meaning is given in parenthesis: The rest of the formulas in MSOL(Σ, Γ) are built from the four different types of atomic formulas by using the standard propositional connectives ∧, ∨, ¬, =⇒ , ⇐⇒ and the standard quantifiers ∀, ∃ in the obvious way with the usual meaning. In particular, the logic is called Monadic Second Order, because we allow quantification over not just vertex variables, but also over vertex-set variables.
Example 2.5.44. We can construct an MSO formula edge(u, v) which expresses the fact that there exists an edge from vertex u to vertex v. It is given by: Using the above formula, we may construct a closed MSO formula edges: Then, H |= edges if the graph H has an edge between any pair of distinct vertices.
Next, we introduce the notion of an MSO definable language, which will play a crucial role in some of the proofs in later chapters. In particular, we shall see that for a fixed string graph, its wire-homeomorphism class is an MSO definable language.
So, any closed MSO formula φ gives rise to a MSO definable language. These languages are the graph grammar analogue of regular languages for standard contextfree string grammars in the sense that they provide the analogous closure property. Context-free string languages are closed under intersection with regular languages and as the next theorem shows, C-edNCE and B-edNCE languages are closed under intersection with MSO definable languages. The above theorem also holds for C-edNCE languages, but it is also true for B-edNCE languages as well, which is the only languages we will be working with. This theorem then can be immediately used in order to obtain some important decidability properties which we shall make use of in the next chapters.

Decidability and Complexity results
In this subsection, we will list some notable decidability and complexity results for VR grammars which we will make use of in the following chapters. In general, B-edNCE grammars are strictly more powerful than context-free string grammars and therefore their decidability and complexity properties are in general worse compared to their string counterparts.
Nevertheless, C-edNCE and B-edNCE grammars enjoy some important decidability properties which we will make use of. One of the most important ones is the decidability of the membership problem. However, the problem is NP-complete in general, even for simple subclasses of ed-NCE grammars, such as the LIN-A-edNCE grammars. Still, there are known efficient algorithms for many special cases.
The next decision problem concerns emptiness and finiteness of grammars which will be used in several proofs. This proposition leads to an interesting corollary. In particular, it shows that we may decide whether the graphs in the language of some grammar all satisfy a fixed MSO formula.
Corollary 2.5.49 ([24]). Let L ∈ B-edNCE be a language generated by a B-edNCE grammar and let R be an MSO definable language. Then, it is decidable whether or not L ∩ R = ∅. Also, it is decidable whether or not L ⊆ R.
Proof. Proof. Any sentential form x 1 x 2 ...x n of G (which may include nonterminals) will be encoded as the following graph: where the vertices between the x i -vertices are dummy terminal vertices, which may be thought of as wire-vertices and the whole graph can thus be seen as a string graph as defined in Section 2.3.
Then, to simulate G, for each production X → x 1 x 2 ...x n of G, we add the following production to G : Thanks to the introduction of the dummy wire-vertices, G is boundary.
Corollary 2.5.51. Given two B-edNCE grammars G 1 and G 2 , it is undecidable Proof. From the last proposition it follows that decidability of language equality for B-edNCE grammars implies decidability of language equality for context-free string grammars. However, that problem is undecidable [28].

Parikh's Theorem
In this subsection, we will introduce Parikh's theorem for C-edNCE languages. Parikh's Theorem was first described by Rohit J. Parikh in [41] for context-free string grammars. It defines a mapping from the language of a grammar to a set of vectors of nonnegative integers. The main result is that this mapping results in a semilinear set, if the grammar is context-free. Parikh's theorem may be used to prove that certain string languages are not context-free. We will use the version of the theorem for graph languages in order to show that certain languages cannot be described using C-edNCE grammars.
In the definition below, we shall denote the set of all nonnegative integers as N and the vector space of all n-tuples of nonnegative integers as N n .
Definition 2.5.52 (Semilinear set [25]). We shall say that a set L ⊆ N n is linear if there exists c ∈ N n and a finite subset P ⊆ N n , such that We will say a set L ⊆ N n is semilinear if it is a finite union of linear sets.
Note, that in the definition of linear set, the vectors x i may appear any finite number of times. So, for P = {x 1 , x 2 , . . . x k }, an equivalent way to define a linear set is: Example 2.5.53. The set: is semilinear, because it is the union of the two sets above, which are both linear.
However, the following set: is not semilinear.
For brevity, we will not present Parikh's theorem for context-free string grammars. Instead, we present the version for context-free graph grammars, which is given in [23]. Definition 2.5.54 (Parikh mapping [23]). For a graph language L ⊆ [GR ∆,Γ ] and a sequence π = (∆ 1 , . . . , ∆ k ) of subsets of ∆, we denote by P ar π (L) the set: In other words, the mapping sends a graph to a vector of nonnegative integers, where each component is just the number of vertices with certain labels. Note, that the mapping ignores edges. The main theorem of this subsection is given next. So, Parikh's theorem establishes necessary conditions for C-edNCE languages and we will use it in the next chapters to show that certain languages are not context-free.
Example 2.5.56. The language of all square grids L: is not a C-edNCE language, because its Parikh mapping is P ar Σ (L) = {n 2 | n ∈ N}, which is not semilinear.

Related Work
A similar approach to using partial adhesive categories (cf. Section 2.2) is using quasiadhesive categories [37]. The two theories are motivated by the same problem -adhesivity is sometimes too strong for categories of interest and a generalisation is needed in order to perform DPO rewriting. Quasiadhesive categories take the approach of requiring that pushouts are stable under regular monos, instead of arbitrary monos.
This generalisation still retains many of the useful properties of adhesive categories. However, in this thesis we use partial adhesive categories, because they are even more general and as we will show we can fully characterise the conditions under which DPO rewriting is well-behaved. This requires more work on our part, but it also allows us to use a larger class of monos over which we can do rewrites.
In this work, we represent string diagrams using string graphs. An alternative approach to reasoning on string diagrams is presented in [7], where the authors use hypergraphs instead. In the string graph representation, the nodes of a string diagram correspond to vertices, whereas in the hypergraph approach, the nodes of a string diagram are represented using hyperedges instead. The main benefits of the hypergraph approach is that it is applicable to any symmetric monoidal category, whereas the string graph approach requires traced structure in addition. In the hypergraph approach the need for considering equality up to wire-homeomorphism is avoided and the category used for rewriting is adhesive, instead of partially adhesive.
However, it is unclear how the hypergraph approach can be lifted to higher-order rewriting, that is, rewriting on families of string diagrams, which is our primary goal in this thesis. As we have seen, many of the languages we are interested in involve families of string diagrams where some of the nodes may have unbounded arity. This would correspond to languages of hypergraphs where some hyperedges are allowed to have unbounded number of tentacles. Hypergraph grammars [18] do not allow for such languages and the author does not know of any other grammars which support this. Therefore, it is likely that a novel kind of hypergraph grammar would have to be developed in order to lift that approach to rewriting on the grammar level.

Context-free Graph Grammars for String Graphs
Our primary goal in this thesis is to develop a framework for equational reasoning with infinite families of string diagrams which is amenable to computer automation.
From previous work, we know how to efficiently represent string diagrams using string graphs [31] and families of string diagrams using !-graphs [40].
In this chapter we will study the expressive power of !-graphs and context-free graph grammars on string graphs. We begin by identifying important limitations of the expressive power of !-graphs in Section 3.1. We use this as a justification to consider an alternative to !-graphs with increased expressive power.
Our first choice for such an alternative is context-free graph grammars (CFGGs) [24]. These grammars have been studied extensively and there is a rich literature of results around them, so this makes them an obvious candidate to consider as an alternative to !-graphs. In Section 3.2, we study the expressive power of CFGGs in relation to !-graphs. The main results are that an important subclass of !-graph languages, namely BGNO (cf. Definition 2.4.22) is properly included in the class of contextfree languages. We also show that !-graph languages and context-free languages are incomparable in general, in the sense that neither class includes the other.
Finally, in Section 3.3, we briefly summarise all of the results by illustrating the overall comparison between the expressive power of context-free graph grammars and !-graphs. We also identify the key limitations of the expressive power of context-free grammars which we will use as a justification to consider a simple extension to their expressive power in later chapters.
Many of the results in this chapter have been previously published in [35].

Limitations of !-graph expressiveness
A very important language for the ZX-calculus is the family of undirected complete string graphs SK n . Each string graph in SK n has n node-vertices each of which is connected to all other node-vertices via a single wire containing a single wire-vertex.
For example, SK 3 is shown below: This language is important for the ZX-calculus as it is the fundamental building block for the local complementation rule of the ZX-calculus, which is very useful when working with the measurement-based quantum computing paradigm [20]. In addition, the local complementation rule is used in the only known decision procedure for deciding equality between ZX-diagrams in the stabilizer fragment of quantum mechanics [2].
However, as we shall see next, SK n cannot be described by !-graphs and therefore this family of string graphs cannot be represented in Quantomatic and cannot be used in any Quantomatic rewrite rules. We shall use this as motivation to consider a more powerful graph generating device.
The more general cause of this limitation is that any !-graph language has bounded chromatic number where we consider the underlying string diagram. This is made precise by the next definition.   Proof. For every string graph H ∈ SK n with n node-vertices, we have χ (H) = n.
Therefore, SK n is of unbounded string graph chromatic number and the language cannot be induced by a !-graph.
We proceed by presenting a severe limitation of !-graph languages. We will show that any !-graph language has a fixed upper bound on the maximum shortest path between a pair of vertices. This notion is usually referred to as graph diameter in the literature, but we make small modifications to the definition in order to suit our purposes.
Definition 3.1.4 (Maximum distance [35]). For a graph H and vertices v, u ∈ H, the distance between u and v is the length of the shortest path connecting u and v.
If there is no path between u and v then we say that the distance is -1. The distance between a vertex and itself is 0. The maximum distance for a graph H is the largest distance among all pairs of vertices.
Definition 3.1.5 (Bounded maximum distance [35]). For a set of graphs L, we say that L is of bounded maximum distance if there exists an integer n ∈ N, such that the maximum distance for every graph in L is smaller than n. If such an n does not exist, then we say that L is of unbounded maximum distance. Proof. Consider a !-box b of H. Applying a KILL operation to b cannot increase the maximum distance. Applying an EXPAND operation once could potentially increase it, however, applying an EXPAND more than once will not increase it any further. Thus, regardless of how many times an EXPAND operation is applied to b the maximum distance can only increase by a fixed amount. Also, because of the symmetric properties of the EXPAND map, any nested !-boxes within b or any overlapping !-boxes can increase the maximum distance with a fixed amount as well regardless of how many EXPAND operations are applied to any of them.
By combining the above observation with the fact that H has finitely many !boxes we can conclude that the set of graphs induced by H is of bounded maximum distance.
In the context of the ZX-calculus, this limitation is severe because it shows that !-graphs can only be used to represent families of quantum circuits with a fixed depth. This corresponds to quantum algorithms and protocols with time complexity O(1). Both of the limitations identified in this section provide a compelling reason to consider alternatives to the !-graph formalism, as we do in the next section.

Expressivity of context-free grammars on string graphs
In this section we outline the relationship between !-graph languages and contextfree languages. In Subsection 3.2.1 we show that the classes of languages induced by (unrestricted) !-graphs and context-free grammars respectively are incomparable. We also make the relationship between !-graphs and CFGGs more explicit by considering some of their subclasses and comparing them. In subsection 3.2.2, we show that the language induced by any !-graph H with no overlapping non-nested !-boxes can be described by a LIN-edNCE grammar, which can moreover be constructed effectively from H.

CFGGs and general !-graphs
We begin by showing that the two most important classes of context-free graph grammars have the same expressive power when restricted to string graphs. For general graphs VR grammars, also known as C-edNCE grammars, are strictly more expressive. Proof. The graph K 3,3 is not a subgraph of any string graph. Then, the proposition follows immediately from the main result in [12].
As we are interested in string graph languages, then it doesn't matter what grammar we choose. However, we will use C-edNCE grammars (and in particular B-edNCE grammars), because in later chapters we will propose a simple extension which increases their expressive power. This extension does not result in increased expressive power for hyperedge replacement grammars and the author does not see how HR grammars may otherwise be extended in order to have satisfactory generative power for our purposes. Because of this, we will use edNCE grammars throughout the thesis. Next, we show that there exists a very simple simple context-free language which cannot be described by any !-graph. Proof. The language generated by G consists of node-vertices connected in a line via a single wire. It is given by: Obviously, this language is of unbounded maximum distance and therefore it cannot be generated by any !-graph.
This proposition shows that CF ⊆ BG, where CF is the set of all context-free string graph languages and BG is the set of all !-graph languages.
Next, we show that there exists an entire class of !-graphs whose languages are not context-free. Let π = ({α}, {β}) and let's consider the Parikh mapping of L. From Theorem 2.5.55, we know that P ar π (L) is semilinear. Without loss of generality we shall assume that w is in b, but not in b . Then: Thus, for every expand operation on the !-box b , we get as many copies of the vertex v as we apply expand operations on the !-box b. However, this language is obviously not semilinear and we get a contradiction.
This proposition may be further generalised by relaxing some of the conditions, but then the proof becomes very involved. In any case, the proposition is enough to show that there is a large class of !-graph languages which are not context-free.
Therefore, this establishes that BG ⊆ CF.
However, as the next proposition shows, there are !-graph languages with nonnested, but overlapping !-boxes which are context-free.
Proposition 3.2.4. Let H be a !-graph of the following form: where K is an arbitrary string graph. b 1 and b 2 overlap on K and b 1 contains another (isomorphic) copy of K, no part of which appears in b 2 . Then, L(H) is the language of a Lin-A-edNCE grammar.
Proof. If we expand the !-boxes b 1 and b 2 , m and n times respectively, then we would get m + mn copies of K. Because we consider all possible sequences of !-box operations when generating a !-graph language, this means that L(H) simply consists of an arbitrary number of copies of K (in other words, we can fix n to be zero). This language can therefore be generated by the Lin-A-edNCE grammar: S X X X X K This proposition shows that overlapping !-boxes do not necessarily imply that the language is not context-free.
Let's denote with SK m,n the language of directed complete bipartite string graphs.
The node-vertices in SK m,n are partitioned into two sets M and N of cardinality m and n respectively. Each node-vertex from M is connected to all other node-vertices of N via a single wire consisting of a single wire-vertex.
SK m,n :=   The next proposition shows that this language can be expressed by a !-graph with trivially overlapping !-boxes, but it is not context-free.

CFGGs and BGNO
The main result of this subsection is a theorem stating that the language induced by any !-graph with no overlapping non-nested !-boxes can be directly represented by a LIN-edNCE grammar, which can moreover be generated effectively.
Before we present the main results in this subsection, we prove a series of lemmas which are used in the proof of the main theorem. Each lemma describes how to build bigger LIN-edNCE grammars out of smaller ones which in turn describe the language induced by certain subgraphs of a given !-graph. All of our constructions are effective in the sense that they can be performed by a computer.
We introduce some conventions that are used throughout our proofs. Given a !-graph H, its vertices will be {v 1 , v 2 , ..., v n }. To these vertices, we will associate edge labels {α 1 , α 2 , ..., α n } which will be used in the productions of our grammars. Informally, an edge labelled with α i will have as its source or target either the original vertex v i or one of its copies. This is used in some productions of our grammars, so that we can easily refer to all copies of such a vertex at once and connect them to other vertices.
In order to prove the main result in this section, we will use edNCE grammars satisfying the conditions detailed in the next definition. This allows us to split the proof into several small lemmas. 2. There exists a function χ : X → ∆ which associates terminal vertex labels for every edge label α i ∈ X .
3. There is a single final production, that is, a production with no nonterminal vertices. The body of this production is simply the empty graph.

Every production with nonterminal vertex x is such that for every terminal
vertex where α i is a unique label associated with v i . Graphically we will depict these edges using bidirectional arrows for compactness.
5. Every production with nonterminal vertex x has connection instructions (σ i , α i , α i , x, in) and (σ i , α i , α i , x, out), where the α i range over X and σ i = χ(α i ). Graphically, we will depict that using bidirectional arrows as a shorthand notation for a connection instruction in each direction. Moreover, because σ i is determined by α i we will not depict the label in the connection instructions for simplicity. Proof. This is done by the following grammar: Proof. Let's assume that S is the initial nonterminal label of G, F is the final nonterminal label of G and that S and F are not production labels used by G.
First, we modify the production labelled F to be the following: Finally, to the productions of G we add the following productions, where S is the initial nonterminal label:  Also, let S i and F i be the starting and final production labels respectively of G i . First, we modify each non-final production of G 1 , by adding connection instructions for edge labels α k+1 , . . . , α n in the following way: where the new additions are coloured in red. This doesn't change the language of G 1 and is done so that we can put the grammar in the required form. Similarly, modify all non-final productions of G 2 by adding to their connection instructions the missing edge labels α 1 , α 2 , . . . , α k .
Finally, modify F 1 to be the production depicted below: so that we can chain together the two grammars.
The required grammar G has as its productions the modified productions of G 1 and G 2 with initial nonterminal label S 1 . A derivation S 1 ⇒ · · · ⇒ F 1 creates a concrete graph from the language of H and a derivation S 2 ⇒ · · · ⇒ F 2 creates a graph from the language of K. By chaining the two grammars, we simply generate two disjoint concrete graphs, one from the language of H and one from the language of K, as required. Proof. In both cases, for the newly depicted edge, identify the wire-vertex as v i and the node-vertex as v j . To get G , identify the unique production of G which contains a vertex incident to an edge with label α j . Then add to its connection instructions a new edge in the following way: X where the red-coloured edge is the new addition. To get the grammar G , follow the same procedure, but with the directions reversed: X In each case, this modification has the effect that we connect all copies of the wire vertex (identified by the connection instruction labelled α i ) to the single node vertex (identified by the edge labelled α j ), which is the only change required compared to the concrete graphs of H. K must be a node-vertex, because otherwise this would violate the openness condition of !-boxes. Let w ∈ K be a wire-vertex that v is adjacent to and let e be the edge connecting v to w.
If v is in some !-box b , then the openness condition of !-boxes implies that w must also be in b . However, we have assumed that H does not contain overlapping !boxes, so this is not possible and thus v is not in any !-boxes. Therefore, we can use lemma 3.

Limitations of context-free graph grammars
We begin by showing a limitation of context-free grammars in terms of their expressive power on string graphs.
which is not semilinear and therefore SK n is not a context-free graph language.
As we have shown before, !-graphs cannot express this language either, nevertheless, this language is important and we would like to be able to formally represent it.
The figure below summarises the results of this chapter: where all regions of the diagram are populated, except for the part between LIN-edNCE and CF inside BG indicated by the dashed red line, which has not been proven, but it is conjectured.
In Section 3.1 we identified two key limitations of !-graphs -they are of bounded diameter and the language SK n cannot be expressed by them. We have shown that context-free graph grammars do not suffer from the former limitation, but they do suffer from the latter. In addition, context-free graph grammars cannot express the language SK m,n which is also crucial. For these reasons, in the next chapter we will introduce a simple extension to our context-free grammars which overcomes these limitations, while retaining many of their structural and decidability properties.

Chapter 4 B-ESG grammars
In this chapter we will introduce B-ESG grammars, which are extended context-free graph grammars. B-ESG grammars are a shorthand for Boundary Encoded String Graph grammars. They are based on B-edNCE grammars and the B in the name has the same intended meaning. We will also show that B-ESG grammars do not suffer from any of the limitations in expressive power that we identified in the previous chapter.
In Section 4.1, we begin by describing encoded B-edNCE grammars. An encoded B-edNCE grammar is a slightly more general B-edNCE grammar. Its derivations consist in two parts -first, a graph is produced in the same way as for standard B-edNCE grammars and then secondly, some of its edges are replaced with fixed graphs according to some additional rules. There are two main results of this section. The first one is that encoded B-edNCE grammars are strictly more expressive compared to context-free graph grammars when we restrict ourselves to string graphs. The second result is that encoded B-edNCE grammars properly include BGTO, which is the class of !-graph languages where non-nested !-boxes may overlap trivially.
Encoded B-edNCE grammars generate languages of (general) graphs. They are not restricted to languages of string graphs. However, our aim is to model string diagrammatic reasoning by representing string graphs, so naturally we are only interested in languages consisting solely of string graphs. In Section 4.2 we will introduce B-ESG grammars, which are encoded B-edNCE grammars which satisfy conditions that ensure their derivations result in string graphs.
In Section 4.3 we show that we do not lose any expressive power, on languages of string graphs, by restricting ourselves to B-ESG grammars from encoded B-edNCE grammars. In particular, we prove that for any encoded B-edNCE grammar which generates a language consisting of string graphs, there exists a B-ESG grammar generating the same language.
Finally, in Section 4.4 we prove important decidability properties for B-ESG grammars. In particular, we prove that the membership and match-enumeration problems are decidable, which are crucial for the operation of a software proof assistant.
Many of the results in this chapter are based on previously published results in [33]. However, since then the results have been improved by the author by generalising the definition of B-ESG grammar.

Encoded B-edNCE grammars
We begin by presenting a refinement of the vertex and edge label alphabets we will use. The new addition is a subset of edge labels E which will denote encoding edge labels. The next definition describes the alphabets we will need for the rest of the chapter and all of our constructions will be over these alphabets.
Definition 4.1.1 (B-ESG alphabets). We will use the following alphabets: 1. Σ is the alphabet of all vertex labels.
3. N ⊆ ∆ is the alphabet of node-vertex labels and W = ∆ − N is the alphabet of wire-vertex labels.
4. Γ is the alphabet of all edge labels. We will not use any non-final edge labels (see Corollary 2.5.33).
5. E Γ is the alphabet of encoding edge labels.
In the previous chapter we saw that C-edNCE grammars cannot represent languages of interest to the ZX-calculus and also entire classes of languages which are expressible using !-graphs while being relevant to the ZX-calculus and other string diagrammatic theories which contain Frobenius algebras. We propose a simple extension to the generative power of C-edNCE grammars with the motivation of overcoming these limitations. The main idea is to use B-edNCE grammars which generate encoded string graphs. These encoded string graphs are just like string graphs, but with the addition that we allow edges to connect node-vertices if they carry encoding labels.
The encoding edges would then be replaced by fixed graphs according to a simple set of rules. Thus, we would use B-edNCE grammars to generate languages of encoded string graphs which are then decoded using a very simple set of DPO rewrite rules to obtain languages of string graphs. Definition 4.1.2 (Encoded string graph [33]). An encoded string graph is a string graph where we additionally allow edges with labels α ∈ E to connect pairs of nodevertices. Edges labelled by some α ∈ E will be called encoding edges.
Definition 4.1.3 (Decoding system [33]). A decoding system T is a set of DPO rewrite rules of the form: where the LHS consists of a single edge with encoding label α ∈ E connecting a σ 1 -labelled node-vertex to a σ 2 -labelled nodevertex, and the RHS is a string graph which contains the same two node-vertices and at least one additional vertex while containing no inputs, outputs, or encoding labels.
Instead of depicting the decoding rules as a span (as we did in the above definition), we will introduce a more compact notation which we shall use from now on when depicting decoding systems. A DPO rewrite rule from a decoding system T : H will be depicted as: That is, we simply take its LHS and RHS. By doing this, we don't lose any information, because the interface of the DPO rule is simply the two node-vertices which are common in both sides. Given an (encoded string) graph, decoding is the process of applying all of the rules of T to the graph. As the above proposition shows, this is a very simple process which may even be done in a single step. If H is an encoded string graph, we shall say that H has been decoded from H, and denote this with H =⇒ T * H , if the graph H is the result of applying all rules from T to H, such that H contains no encoding edges. Next, we present a lemma which establishes a relationship between encoded string graphs, the process of decoding and string graphs. (⇐=) H cannot contain a wire-vertex v with in-degree (out-degree) more than one, because otherwise so does H as decoding will not add, nor remove any neighbours of v. If H contains an edge between a pair of node-vertices with label α ∈ E, then so does H as T will preserve this edge. Therefore, H must be an encoded string graph.
The horizontal derivation sequence is simply a concrete derivation in the B-edNCE grammar. Once that is done, the vertical derivation step simply decodes all of the encoding edges, as specified by the decoding system.
Recall that both languages SK m,n and SK n were considered in the previous chapter and we highlighted their importance. However, we showed that neither of them can be described by context-free graph grammars. Now we see that the simple extension which we introduced (the addition of the decoding system) allows us to represent them. Using this fact, the next proposition follows immediately. Proof. Obviously, any B-edNCE grammar G may be simulated by an encoded B-edNCE grammar B = (G, ∅), that is, the alphabet of encoding labels is empty and therefore so is the decoding system. Then, the proposition follows after considering the language from Example 4.1.8 or Example 4.1.9.
Therefore, encoded B-edNCE grammars are indeed more powerful compared to B-edNCE grammars in general. Also, recall that B-edNCE C-edNCE = CF.
Since we are only interested in string graph languages, a natural question to ask is if encoded B-edNCE grammars are more powerful compared to context-free graph grammars when we restrict ourselves to string graphs. The next theorem shows that this is indeed the case. We can provide a more detailed picture of the expressive power of encoded B-edNCE grammars by comparing them to !-graphs. Recall that context-free string graph languages contain the class BGNO, but they do not contain BGTO. However, we can show that encoded B-edNCE grammars properly include the class BGTO, which in turn contains BGNO. The rest of the section is devoted to proving this result.
We will show this result by building on the proof from Subsection 3.2.2. First, we generalise the definition of !-linear form to encoded B-edNCE grammars.
Definition 4.1.12 (!-encoded grammar). We will say that an encoded B-edNCE The next lemma is similar in spirit to the lemmas of Subsection 3.2.2. It shows how to construct a larger !-encoded grammar from a smaller one, both of which simulate the languages of !-graphs which differ by the addition of a wire in a trivially overlapping pair of !-boxes. Proof. For the newly depicted edges whose source or target are the two node-vertices, identify the source node-vertex as v i and the target node-vertex as v j . To get the desired grammar G , identify the unique production X of G, such that X contains a vertex incident to an edge with label α j . Then, add to its connection instructions a new edge with unique label β k : where the new addition is coloured in red. Note, that with this construction, we are not creating the newly depicted wire-vertices, nor any of their copies. We are connecting all copies of the node-vertex v i to all copies of the node-vertex v j directly with edges labelled with β p .
Therefore, the grammar G as described so far will generate encoded string graphs which connect all copies of the vertex v i to all copies of the vertex v j via edges with label β k (the edges with label β i , with i < k have been established by the same construction in previous steps). What remains is to decode the edges labelled β k .
Thus, to get the same language as that of H, we need to add to T the decoding rule: β k ⇒ where the right-hand side contains the same closed-wire (coloured in red above) which has been added to H.
Next, we present the main theorem of this section. It combines the previous lemma with the results of Subsection 3.2.2 to derive the result.

B-ESG grammars and their languages
Our goal in this thesis is to model string diagrammatic reasoning. We also wish to implement machine support for the reasoning process, so we have to identify decidable conditions on our grammars which imply that they generate string graphs only. In the previous section we saw that encoded B-edNCE grammars have satisfactory expressive power. In this section, we will identify sufficient conditions on the productions of an encoded B-edNCE grammar which ensure that it can only generate string graphs.
The grammars which satisfy these conditions are called B-ESG grammars.
We begin by introducing a few auxiliary definitions that will help us to introduce our first major notion, called wire-consistency. We will first define wire-consistency in terms of the structure of a grammar and show that it is a decidable property. After that, we will provide a dynamic characterisation -we will show how the sentential forms of wire-consistent grammars behave. Definition 4.2.2 (Context-cardinality). Given a production p of a B-edNCE grammar G, where p contains a vertex x, we say that its (σ, β, d) context-cardinality is n if the number of (σ, β, d)-edges incident to x plus the number of connection instructions of the form (σ, α, β, x, d) is equal to n.

Definition 4.2.3 (Context-passing). Given a B-edNCE grammar G, terminal vertex
label σ ∈ ∆, edge labels α, β ∈ Γ and direction d ∈ {in, out}, we define a binary relation P d σ (α, β) between nonterminal vertices x, y in productions p 1 , p 2 of G respectively. We will refer to P as the single-step context-passing relation. We say x P d σ (α, β) y, if: • x has context-cardinality (σ, α, d) at least one • p 2 has the same production label as that of x • there exists a connection instruction (σ, α, β, y, d) in p 2 We define the multi-step context-passing relation to be Q d σ (α, α ) again between a pair of nonterminal vertices. We will say x Q d σ (α, α ) x if there exist nonterminal vertices x 1 , . . . , x n and edge labels α 1 , . . . , α n , such that: To be more precise, both P and Q are actually a family of binary relations, which are parametrised over σ ∈ ∆, α ∈ Γ, α ∈ Γ, d ∈ {in, out}. Instead of defining them as relations over a 6-tuple of sets, we opt for this notation as it is more convenient for showing the next proposition. where x, y, z are the nonterminal vertices with labels X, Y, Z respectively. Then, x P in σ (α, β) y and y P in σ (β, γ) z. This also means x Q in σ (α, γ) z.
Proposition 4.2.6. For a given B-edNCE grammar G, the multi-step context-passing relation Q is computable.
Proof. Fix a direction d and vertex label σ. Define a new relation Q 0 , such that for every α, β ∈ Γ, we have: In other words, Q 0 (α, β) = P d σ (α, β). P is obviously computable and therefore so is Q 0 . Next, having already computed Q n , we define: x Q n+1 (α, β) y iff (x Q n (α, β) y) ∨ ∃z, γ. x Q n (α, γ) z ∧ z P d σ (γ, β) y The computation stops when we find a k such that Q k+1 = Q k . Note, that this procedure is guaranteed to terminate, as we have finitely many nonterminal vertices, exactly two possible directions and finitely many labels and each step of the procedure increases the size of the relation, except for the last one.
We claim that upon termination, Q k (α, β) = Q d σ (α, β). In one direction, this is easy to see: if x Q k (α, β) y, then obviously also x Q d σ (α, β) y holds by construction of Q i .
Now we can introduce wire-consistency. Note that the previous proposition implies that wire-consistency for a B-edNCE grammar is a decidable property.
Definition 4.2.7 (Wire-consistent grammar). We say a B-edNCE grammar G is wireconsistent, if for every production p of G, every σ ∈ ∆, α ∈ Γ, β ∈ Γ, d ∈ {in, out} and every nonterminal vertex x of p with context cardinality (σ, α, d) at least two, the following holds: every production with label in the set {λ(y) | x Q d σ (α, β) y} cannot have a connection instruction (σ, β, γ, z, d) where z is a wire-vertex and γ ∈ Γ.
This definition provides a static description of wire-consistency. Its purpose is to show that this notion is decidable, however this definition is rather cumbersome to work with. What we will find more useful is the dynamic description of wireconsistency which is presented in Lemma 4.2.9. Simply put, a grammar is wireconsistent if each connection instruction attached to a wire-vertex can establish at most one bridge in any derivation. This is clearly a necessary property, because string graphs cannot have wire-vertices with in-degree (out-degree) more than one.
So, we see that the wire-vertex established at the end has in-degree two, despite the fact that in production p 4 the wire-vertex has a single connection instruction associated to it.
The next lemma is crucial, because it shows that the scenario from the previous example is impossible -wire-consistent grammars ensure that connection instructions associated to a wire-vertex cannot create more than one bridge to the same wirevertex, in any derivation.
Lemma 4.2.9. Given a wire-consistent grammar G and a sentential form H = (D 1 , C 1 ), then applying any production p = X → (D 2 , C 2 ) to H has the following effect: for any σ ∈ ∆, β ∈ Γ, d ∈ {in, out} and any wire-vertex w ∈ D 2 the substitution process will establish at most one (σ, β, d)-bridge between w and D 1 using any connection instruction (σ, α, β, w, d) ∈ C 2 , where α ∈ Γ. H is a sentential form, then it must be the yield of a derivation tree T . Thus, H = yield(T ). Because G is a B-edNCE grammar, observe that only the productions in T which are a predecessor of p in T may affect the neighbourhood of w. The other productions replace nonterminal vertices which cannot be connected to w. So, without loss of generality, we can assume: where all the listed productions are (not necessarily direct) predecessors of p in T (see If both v, v ∈ H n−1 then they are both in the body of production p n . Hence, the nonterminal node x in p n must have context-cardinality (σ, α, d) equal to 2 which then contradicts with G being wire-consistent.  If v ∈ H n−1 but v ∈ H n−1 , then v is a vertex in the body of p n connected to the nonterminal x (via edge labelled α) and p n must have a connection instruction of the form (σ, α , α, x, d). Again, the nonterminal x in p n has context-cardinality (σ, α, d) equal to 2 which contradicts with G being wire-consistent.
Thus, both v, v ∈ H n−1 and the production p n must have a connection instruction (σ, α , α, x, d), for some α ∈ Γ.
By iterating this argument, we conclude that the nonterminal vertices x 1 , . . . , x n in productions p 0 , . . . , p n−1 satisfy the context-passing relation x i Q d σ (α, β) x and that the two vertices v and v must be created by the initial production p 0 and must be connected to the nonterminal x 1 via a (σ, α , d)-edge. However, H 1 is the body of production p 0 . Thus, the nonterminal x 1 in the body of p 0 has (σ, α , d) context cardinality equal to at least 2. At the same time we know x 1 Q d σ (α, β) x for productions p 0 and p n and then we get a contradiction with the fact that G is wire-consistent.
In other words, during the derivation process, a wire-consistent grammar can establish at most one bridge between a newly created wire-vertex and the previously generated graph for a single connection instruction associated to that wire-vertex.
We only need to introduce one additional notion before we can classify the grammars we are interested in.
Definition 4.2.10 (Production degree). Given a B-edNCE grammar G and a production X → (D, C) with vertex v ∈ D, the connection instruction in-degree of v is the number of connection instructions (σ, α, β, v, in), for some σ ∈ Σ, α, β ∈ Γ. Similarly, the connection instruction out-degree of v is the number of connection instructions (σ, α, β, v, out), for some σ ∈ Σ, α, β ∈ Γ. The production in-degree (production outdegree) of v is the sum of the connection instruction in-degree (connection instruction out-degree) and the in-degree (out-degree) of v. the X-labelled vertex has production in-degree two, the Y -labelled vertex has production in-degree two, the Z-labelled vertex has production in-degree one, the wirevertex has production in-degree one and the two σ-labelled vertices have production out-degrees one.
We can now provide the central definition of this chapter. The conditions N1 and N2 guarantee that node-vertices never become directly connected by an edge, unless that edge has an encoding label. Conditions W1 and W2 together with wire-consistency ensure that wires never split, i.e. wire-vertices always have in-degree (out-degree) at most one.
Before we present the main result of this section, we introduce a helpful definition which describes the sentential forms of B-ESG grammars.
Definition 4.2.13 (ESG-form [33]). Given a B-edNCE grammar G, we call a sentential form an ESG-form (Encoded String Graph form) if it is an encoded string graph, which possibly has some additional nonterminals that are either connected to node-vertices or are connected to wire-vertices in such a way that all wire-vertices have in-degree (out-degree) at most one.
Example 4.2.14. Consider the following two graphs:

X X
The graph on the left is an ESG-form, but the graph on the right is not, as it contains a wire-vertex with in-degree two.
We can now prove the main theorem of this section which shows that the language of any B-ESG grammar consists of string graphs only. Proof. Let B = (G, T ) be a B-ESG grammar and let's consider an arbitrary concrete derivation S = H 1 =⇒ G x 1 ,p 1 H 2 =⇒ G x 2 ,p 2 · · · =⇒ G xn,pn H n =⇒ T * F . Using Lemma 4.1.5 we can reduce the problem to showing that H n is an encoded string graph. We will prove, using induction, that every graph H i is an ESG-form. From this, the theorem follows immediately, because H n is an ESG-form with no nonterminal vertices which means it is simply an encoded string graph.
In the base case, H 1 contains only the initial nonterminal S and it is obviously an ESG-form. Assuming that H k is an ESG-form, let's consider H k+1 which is the result of applying production p k at vertex x k in H k .
Condition N2 guarantees that any newly created node-vertices in H k+1 will be adjacent to the previously established node-vertices in H k only via encoding bridges.
In addition to this, condition N1 ensures that the newly created node-vertices in H k+1 can be adjacent to other newly created node-vertices only if the connecting edges have encoding labels. Combining this with the fact that H k is an ESG-form means that all node-vertices in H k+1 can only be adjacent to other node-vertices via encoding edges, as required.
Next, we will show how the dynamic behaviour on newly established wire-vertices is influenced by condition W1 and the wire-consistency of the grammar G. For a newly created wire-vertex w in H k+1 , we consider two cases and examine its indegree. If w is incident to an in-edge with another newly created vertex in H k+1 , then condition W1 ensures that this is the only in-edge of w and that it is not connected to any previously established vertices in H k . If w has at least one in-edge with some previously created vertices in H k , then condition W1 guarantees that all of the inedges of w have been established by consuming a single connection instruction. Then, using Lemma 4.2.9, we conclude that the in-degree of w is exactly one. Using the same arguments for out-edges we conclude that any newly created wire-vertex in H k+1 can have in-degree at most one and out-degree at most one. Note, that it is possible for newly created wire-vertices to have in-degree (out-degree) zero when their production in-degree (out-degree) is zero.
Condition W2 prevents increasing the in-degree or out-degree of previously established wire-vertices in H k . Combining this with the previous results and the induction hypothesis, we get that all wire-vertices in H k+1 have in-degree or out-degree at most one. All of this together means that H k+1 is an ESG-form.

Expressivity of B-ESG grammars
In the previous section we introduced B-ESG grammars which are simply encoded B-edNCE grammars that satisfy some additional conditions. These conditions ensure that B-ESG grammars generate only string graphs. It is not immediately obvious whether these conditions are restrictive in the sense that B-ESG grammars would not be able to simulate some encoded B-edNCE grammars. In this section we will show that this is not the case -B-ESG grammars have the same expressive power as encoded B-edNCE grammars on string graphs. Proof. The grammar G can be constructed effectively from G by using Theorem 2.5.42.
That is, we consider an equivalent grammar in CNF form. We have to show that G satisfies Definition 4.2.12.
Since L(G ) = L(G), then using the fact that G never establishes blocking edges, we conclude that all terminal sentential forms of G are encoded string graphs (again, by using Lemma 4.1.5).
Next, we can show that all sentential forms of G are ESG-forms. We can show this by contradiction -if there exists an ESG-form H which contains a wire-vertex with in-degree (out-degree) more than one, then for any concrete derivation H =⇒ * H , H will also contain a wire-vertex with in-degree (out-degree) more than one, because G is neighbourhood-preserving (the degree of vertices cannot decrease during a derivation). However, this contradicts with the fact that all terminal sentential forms of G are encoded string graphs. The other case to consider is when H contains a nonencoding edge between a pair of node-vertices. But then, for any concrete derivation H =⇒ * H , H will also contain an edge with nonencoding label connecting a pair of node-vertices, so we establish a contradiction again. Thus, all sentential forms of G are ESG-forms.
Let's consider an arbitrary production p = X → (D, C) of G . G is reduced, therefore there exists a derivation S =⇒ * H 1 =⇒ x,p H 2 .
If p violates condition N1, then p establishes two new node-vertices which are connected via a non-encoding edge. Therefore, H 2 is not an ESG-form and we get a contradiction.
Let's assume p violates condition N2. Therefore, p contains a connection instruction (N, α, β, v, d), where N ∈ N , v is a node-vertex in rhs(p) and β ∈ E.
G is context consistent and contains no useless connection instructions, therefore (N, α, d) ∈ cont H 1 (x). This means that applying production p to H 1 will establish a nonencoding edge between two node-vertices and we get a contradiction with the fact that H 2 must be an ESG-form.
Assume p violates condition W1. Without loss of generality, let's assume the offending wire-vertex w has connection in-degree n and in-degree m in D with m+n > 1. As in the previous case, by using context consistency and the fact that G doesn't have useless connection instructions, we see that applying p to H 1 will create at least n in-edges to the newly created wire-vertex w via the embedding process. However, w also has an additional m in-edges in D and therefore its in-degree in H 2 is at least m + n > 1 which is a contradiction with the fact that H 2 is an ESG-form.
Assume p violates condition W2. Therefore, we may assume, without loss of generality, that there are two connection instructions (W, γ, δ 1 , x 1 , in), (W, γ, δ 2 , x 2 , in), where the δ i and x i are not necessarily distinct. Again, by making use of context consistency and the fact that G has no useless connection instructions, we get that the nonterminal x in H 1 must have a γ-labelled in-edge adjacent to a W -labelled wire-vertex y. Then, applying production p to H 1 will make the out-degree of the wire-vertex y to be equal to two in H 2 . This is a contradiction with the fact that H 2 is an ESG-form.
Finally, let's assume that G is not wire-consistent. Without loss of generality, there exists a production p, such that it contains some nonterminal vertex x which has context cardinality (σ, α, in) equal to two. Because G is reduced, there must exist a derivation S =⇒ * H 1 =⇒ p H 2 . By making use of the same arguments as in the previous cases (no useless connection instructions, context consistency) we see that the nonterminal x in H 2 must have two α−labelled in-edges incident to two σ-labelled vertices. Let's call these two σ-labelled vertices v and u. Since we have assumed that G is not wire-consistent, there exists a production p which contains a nonterminal vertex y which is in the context-passing relation with x, that is x Q in σ (α, β) y, for some β ∈ Γ. Then, there must exist a derivation: where the production p creates a nonterminal vertex y, which, thanks to the contextpassing assumption, will have two β-labelled in-edges incident to the previously established vertices v and u (which have the same label). Finally, by assumption, there must exist a production p with production label the same as that of y which moreover must have a connection instruction (σ, β, γ, z, in) for some γ ∈ Γ and where z is a wire-vertex. Applying production p to H 4 would therefore result in a graph where the wire-vertex z has in-degree more than one (it would be adjacent to both u and v) which is a contradiction with the fact that all sentential forms of G are ESG-forms. Therefore, B-ESG grammars have the same generating power as encoded B-edNCE grammars (on string graphs). However, unlike (general) encoded B-edNCE grammars, B-ESG grammars can only generate string graphs. Therefore, for our purposes, this

Decidability properties of B-ESG grammars
When working with families of string diagrams, it is necessary to be able to determine whether a given concrete diagram is an instance of a given family of diagrams. In terms of string graphs and B-ESG grammars, this means that we should be able to decide whether a given string (up to wire-homeomorphism) is in the language of a B-ESG grammar. This is the membership problem for B-ESG grammars, which we will show is decidable in this section.
Another problem which is crucial is the ability to enumerate all the matches of all instances of an equational schema into a concrete diagram, so that we can rewrite it. In terms of string graphs and B-ESG grammars, this means that given a B-ESG grammar B and a string graph H, we should be able to enumerate all derivations S =⇒ B * F , and all matches F → H (up to wire-homeomorphism). This is the match enumeration problem which we will also show is decidable. Note, that decidability of this problem implies decidability of the membership problem.
To show that these problems are decidable, we will use a logical description (cf. Subsection 2.5.5) of the wire-homeomorphism class of a given encoded string graph. In particular, we will first show that for given an encoded string graph H, we can effectively construct a closed MSO formula φ H , such that L(φ H ) = [H] ∼ , that is, the MSO language which the formula induces is the wire-homeomorphism class of H.

Wire-homeomorphism as MSO definable language
We begin by proving a few lemmas which are helpful for establishing the mentioned logical characterisation. Recall that we assume our labelling alphabets Σ and Γ are finite. This is necessary for the decidability of the problems we are interested in. • edge(u,v) : There exists an edge between u and v.
• encoding-edge(u,v) : There exists an edge between u and v which carries an encoding label.
• non-encoding-edge(u,v) : There exists an edge between u and v which carries a non-encoding label.
• node-vertex(u) : u is a node-vertex.  1. There exists no non-encoding edge between two node-vertices 2. The in-degree of any wire-vertex is at most one 3. The out-degree of any wire-vertex is at most one Each of those three conditions can easily be encoded using MSO logic. The formula is given by: where each line represents one of the three conditions. Proof. Follows immediately from Lemma 5.2.7, pp. 327 of [13]. In particular, wire-edge + (u, v) is given by: Proof. It is given by : The next definition generalises the notion of wire-homeomorphism from string graphs to encoded string graphs. The two notions are essentially the same -two encoded string graphs are wire-homeomorphic if one can be obtained from the other by increasing or decreasing the length of some wires. The main theorem of this subsection is proved next. Proof. H can easily be transformed into the minimal representative of its wirehomeomorphism class, so we assume without loss of generality that H is minimal in that sense. Let H have n node-vertices, given by u 1 , . . . , u n and m wire-vertices given by w 1 , . . . , w m . First, we express the fact that φ H should not be satisfied by graphs with more than n node-vertices. This is given by the following formula : The general form of φ H is given by the following : where the ψ k are some MSO formulas (which can depend on the free u i and w j variables) that are described below.
So far, we can see that φ H will be satisfied by encoded string graphs which have exactly n node-vertices and at least m wire-vertices.
Next, we add constraints on the edges incident to node-vertices on both ends. Let the parallel edges between vertices u i , u j ∈ V H , be indexed by a set I i,j . Thus, the set of edges with source u i and target u j in H is given by H is an encoded string graph, then we must have I i,j ⊆ E, that is all these edges must have encoding labels. Therefore, for each u i and u j , with i = j, we must have the following formula in φ H (as one of the ψ k ) : which describes precisely what edges are allowed and required between a pair of node-vertices. Note, that our notion of graph does not allow for loops on vertices and because of that there's no need to consider the case when u i and u j are the same vertex.
Next, we describe the wires and isolated wire-vertices which any graph satisfying φ H is required to have. For each wire-vertex w i ∈ H, we consider all possible cases of its neighbourhood in H and for each case we add an MSO formula as one of the ψ k denoted above.
If w i is an isolated wire-vertex, then we add the following formula: If w i is an input and has an out-edge to a wire-vertex w j , then w j must be an output and we add the following formula: If w i is an input and has an out-edge to the node-vertex u j , then we add the following formula: If w i is an output and has an in-edge from the node-vertex u j , then we add the following formula: The next case we have to consider is when w i is neither an input, nor an output and it is adjacent to two node-vertices. Let the in-edge of w i be from the vertex u j and its out-edge to the vertex u p . Then, we add the following formula: The final case we have to consider for wire-vertex w i is when w i is neither an input, nor an output and it is adjacent to a single wire-vertex w j , forming a circle of length two (cf. Definition 2.3.10). Then, we add: Finally, we restrict the kinds of wires and isolated wire-vertices allowed in φ H to be exactly the ones given by H. This is the final formula which we add as the last of the ψ k denoted above: which simply says that any wire-vertex must either be one of the already described isolated wire-vertices or part of a wire which is already described in φ H .
From the background chapter we know that MSO definable languages have important decidability properties in relation to context-free languages. We will use this fact for the proofs in the following subsections.

Membership problem
In this subsection we will show that the membership problem for B-ESG grammars is decidable. We will do this by showing that for a given string graph, there are finitely many sentential forms of a B-ESG grammar which need to be considered. In turn, we can prove this by defining appropriate functions which measure the size of a graph and its wire-homeomorphic class and proving some simple properties about them. Moreover, we define a partial-order when working with wsize by (n 1 , w 1 , i 1 ) ≤ (n 2 , w 2 , i 2 ) iff n 1 ≤ n 2 , w 1 ≤ w 2 and i 1 ≤ i 2 . Proof. Wire-homeomorphic encoded string graphs only differ in the number of wirevertices on each wire. Therefore, the three mentioned counts must be the same.
Note, that wsize(H) does not count the number of encoding edges of H, even though wire-homeomorphic encoded string graphs also have equal numbers of encoding edges. This is a deliberate choice as it allows for more elegant proofs in the next few lemmas and theorems. Proof. H 2 is obtained from H 1 by replacing encoding edges (which don't count as wires) by other graphs. Therefore, the numbers of node-vertices, wires and isolated wire-vertices cannot be decreased. Lemma 4.4.11. Given a decoding system T and encoded string graphs such that Proof. H 1 and H 2 only differ in the length of their wires. Therefore, after decoding both graphs, they will again only differ in the length of the same wires.
In our goal to model reasoning with families of string diagrams, we need to be able to decide when a string diagram is a specific instance of a string diagram family.
Recall, that any two string graphs which are wire-homeomorphic represent the same string diagram. Because of this, the membership problem needs to be stated up to wire-homeomorphism.  Proof. Let B = (G, T ) and let H be an arbitrary string graph. For this proof, we will be using the decidability results from Subsection 2.5.6.
First, we show that exact membership (i.e. not up to wire-homeomorphism) is decidable. That is, we have to decide if H ∈ L(B). From Theorem 4.2.15, we know that any concrete B-ESG derivation produces an encoded string graph which is then decoded to a string graph. Since the decoding sequence cannot decrease the size of a graph, we can limit the problem to considering all graphs of size smaller than H.
However, there are finitely many graphs whose size is smaller than H. For each such graph H , we can then decide if H ∈ L(G) (this is the membership problem for B-edNCE grammars). Finally, we check if H =⇒ T * H which is also clearly decidable. If no such graph H exists, then the answer is no and otherwise the answer is yes.
We now generalise to the wire-homeomorphic case. Using Theorem 4.4.6, we know that the wire-homeomorphism class of any encoded string graph K is MSO definable and moreover, we can effectively construct that MSO formula. Therefore, we can decide if L(G) ∩ [K] ∼ = ∅, and moreover, we can also decide if L(G) ∩ [K] ∼ is finite. This immediately implies that we can decide, given an encoded string graph K, whether there exists K , such that K ∼ K ∈ L(G) and if there are finitely many such K .
Let us consider the encoded string graphs K which could possibly be decoded into a wire-homeomorphic string graph of H. From Lemma 4.4.10, any such graph K must satisfy wsize(K) ≤ wsize(H) and therefore we should limit our search to these kinds of encoded string graphs.
If we could consider all encoded string graphs K with wsize(K) ≤ wsize(H), then we could check if K =⇒ T * K ∼ H and if K ∈ L(G) and therefore decide the problem. However, that is impossible, because there are infinitely many such encoded string graphs. But, observe that there are finitely many wire-homeomorphism classes [K] ∼ where each representative has wsize at most that of H (cf. Lemma 4.4.9). Thus, by using Lemma 4.4.11, we see it doesn't matter which representative of the wire-homeomorphism class we choose. Therefore, we can decide the problem by enumerating all minimal representatives of the wire-homeomorphism classes of encoded string graphs with wsize at most that of H. Then, for each minimal representative K, we decide if there exists K , such that K ∼ K ∈ L(G) and if K =⇒ T * K ∼ H. If no such minimal representative exists, then the answer is negative. If we find at least one such representative, then we can also construct a derivation S =⇒ * K ∼ H because derivation sequences are recursively enumerable.
In addition, we can also decide if there are finitely many such K . We have already pointed out that we can decide if there are finitely many K such that K ∼ K ∈ L(G). Combining this with Lemma 4.4.11 means we only have to check if a single representative decodes to a wire-homeomorphic graph of H and therefore we can correctly decide the problem. In the case there are finitely many K (and thus K ), then again we can construct a concrete derivation for each of them because derivation sequences are recursively enumerable.
As we have pointed out previously, the match enumeration problem supersedes the membership problem. However, we will use the decidability of the membership problem in order to show decidability of the match enumeration problem.

Match enumeration problem
Consider the following problem -we are given an equational schema F 1 = F 2 between two families of string diagrams, and we are given a concrete string diagram D. We wish to apply an instance of the equational schema to D, so that we can rewrite it.
In order to do so, we have to identify an appropriate instance I of F 1 and then a monomorphism m : I → D which is a match. However, it is possible that there are multiple instances I, so ideally we want to enumerate all of them, so that we can later decide which one is the most appropriate to use for rewriting. This is the problem which we will show how to solve in this subsection. However, we still haven't explained how to represent equational schemas using B-ESG grammars. This is done in the next chapter. In this subsection we will show how to enumerate all possible instances I of a family F 1 such that there exists a mono m : I → D. This immediately implies we can solve the match-enumeration problem, because we simply have to check if the mono m satisfies the matching conditions, which as we have shown in Section 2.3 are decidable.
The match enumeration problem is not decidable for arbitrary B-ESG grammars.
However, it is decidable for grammars which satisfy some simple conditions. Conditions (2) and (3)  where p is applied at least n times.
Whether a production is iterable can be decided in the same way as for contextfree string grammars. We simply create a graph whose vertices are the productions of the grammar and whose edges indicate possible transitions between productions.
Then, a production is iterable if it is in the same connected component as one of the initial productions and it is part of a cycle.
The next proposition presents sufficient decidable conditions for property (1) from Definition 4.4.14. Proof. Every wire-vertex in the productions of G is not adjacent to nonterminals and has no associated connection instructions. Therefore, the neighbourhood of each wirevertex in any sentential form of G is the same as the neighbourhood of the production which created it. Thus, each isolated wire-vertex and each bare wire are created by a single application of a production of G. The non-iterable productions can clearly produce a finite number of isolated wire-vertices and bare wires, whereas the iterable productions cannot produce any bare wires, nor isolated wire-vertices. Decoding cannot introduce new inputs or outputs and thus the proposition follows.
Next, we define the problem which we need to decide in terms of B-ESG grammars and string graphs.  H as required.
In general for any K ∼ K we may construct the required mono m by simply applying the above argument multiple times. Proof. Let w be the number of wires in a string graph H and let n be the number of its node-vertices. Then, for any H ∼ H, we know that H must have the same number of wires and node-vertices as H. However, the number of wire-vertices in H may be arbitrarily large.
Condition (1) of Definition 4.4.14 implies that there exists m ∈ N, such that, for any K ∈ L(B), K has at most m bare wires. Any mono between string graphs will map at most two non-bare wires onto a single wire. So, if there exists a mono m : K → H, then K can have at most 2w non-bare wires. Therefore, K can have at most 2w + m wires. Moreover, Condition (1) of Definition 4.4.14 also imposes a bound on the number of isolated wire-vertices in K, which we shall assume to be i ∈ N. Clearly, the number of node-vertices in K is also bounded by the number of node-vertices in H. Thus, for any K ∈ L(B) which could possibly have a mono onto some H ∼ H, we know wsize(K) ≤ (n, 2w + m, i  (2) and (3) from Definition 4.4.14 imply that the sentential forms of B can only increase in size and therefore for any K satisfying the above conditions there are finitely many concrete derivations S =⇒ B * K which we can enumerate.
So, if we are using a match-exhaustive B-ESG grammar G, then we can decide the mono-enumeration problem, which immediately implies that we can decide the match-enumeration problem as well.

Related work
The idea of an encoded B-edNCE grammar is similar to the type of graph grammar presented in [44]. There, the author uses a node-replacement graph grammar for which he proposes two different extensions. One of the extensions replaces specially labelled terminal vertices with graphs in a way specified by a separate rule system.
His extension is different from ours in that the rule system is more complicated and replacement is done on vertices, instead of edges. Also, the notion of grammar which he uses is less powerful than ours.
We introduced B-ESG grammars and encoded B-edNCE grammars, because we wish to have more expressive power than standard B-edNCE grammars. Adaptive star grammars are introduced in [19] with the motivation that both hyperedge replacement and vertex replacement graph grammars have limited expressive power. Adaptive star grammars are able to capture a much larger class of graph languages compared to B-edNCE grammars, while also retaining important decidability properties such as membership. However, little is known about their structural properties or normal forms which makes them difficult to reason about in the context of this thesis.

Chapter 5 Rewriting B-ESG grammars
In the previous chapters we introduced B-ESG grammars and showed that they correctly represent families of string diagrams, we argued they have sufficient expressive power and we established they have the necessary decidability properties for rewriting concrete string diagrams. In this chapter we will build upon these results by showing that B-ESG grammars can also be used to rewrite B-ESG grammars themselves in a way which correctly represents equational reasoning on infinite families of string diagrams.
In In this section the distinction between wire-vertices and node-vertices or encoding edges and non-encoding edges is irrelevant. All of our constructions will be over the following labelling alphabets, which are compatible with B-ESG alphabets.
Definition 5.1.1 (Labelling alphabets). Throughout this section, our constructions will be over a triple of labelling alphabets A = (Σ, ∆, Γ), where: 1. Σ is the alphabet of all vertex labels.

∆ ⊆ Σ is the alphabet of terminal vertex labels.
3. Γ is the alphabet of all edge labels. We will not use any non-final edge labels (see Corollary 2.5.33).

Multi-edNCE grammars
Recall that an extended graph (cf. Definition 2.5.3) is simply a graph where, in addition, we can attach connection instructions to its vertices. Parallel edges with the same labels or parallel connection instructions with the same label are not allowed.
We may generalise the definition of extended graphs to allow such parallel edges and parallel connection instructions by analogy to the generalisation of graphs to multigraphs.
Definition 5.1.2 (Unlabelled Extended Multigraphs). The category of unlabelled extended multigraphs is UExtMultiGraph. This category is defined as the functor category [GR, Set], where GR is the category given by: The only non-trivial morphisms in GR are the ones shown in the diagram and we do not require that s and t commute. s and t should be seen as the source and target functions which assign a source or target vertex to edges, c 0 should be seen as assigning a vertex to an in-connection instruction and c 1 should be seen as assigning a vertex to an out-connection instruction. In most scenarios we would, of course, have s = t. For an extended multigraph H ∈ UExtMultiGraph, we shall denote with V H its set of vertices, with E H the set of its edges, with C 0 H the set of its in-connection instructions and with C 1 H the set of its out-connection instructions. l E : E G → Γ (the edge labelling function)

the out-connection instruction labelling function)
A morphism between two extended multigraphs f : (G, l) → (H, l ) is a morphism f : G → H of UMultiExtGraph, which in addition respects the labelling, that is the following diagrams commute: Building on top of this, we may generalise edNCE grammars to multi-edNCE grammars. What is left is to partition all the vertices, edges and connection instructions into productions.
The only non-trivial morphisms in EDNCE are the ones shown in the diagram. Again, we do not require that s and t commute, however we do require that the rest of the diagram commutes, that is: For a multi-edNCE grammar G ∈ UMultiEdNCE, we shall denote with V G its set of vertices, with E G the set of its edges, with C 0 G the set of its in-connection instructions, with C 1 G the set of its out-connection instructions and with P G the set of its productions.
In the definition above, we shall refer to the morphisms s and t as the source and target functions. They assign each edge e ∈ E G a source and target vertex respectively. An edge e is said to be incident to a vertex v, if s(e) = v or t(e) = v.
The morphism c 0 assigns to each in-connection instruction c ∈ C 0 G a vertex v ∈ V G . Similarly, the morphism c 1 assigns to each out-connection instruction c ∈ C 1 G a vertex v ∈ V G . We will say that a connection instruction The newly introduced morphisms in EDNCE, p E and p V assign edges and vertices respectively to a production p ∈ P G of our grammar. We will say that a vertex v is in a production p ∈ P G if p V (v) = p and we will say that an edge e is in a production p ∈ P G if p E (e) = p. The commutativity requirements imposed by the diagram ensure that if an edge e is assigned to a production p, then both its source vertex s(e) and its target vertex t(e) are also in p.
A component X G of G is either its set of vertices V G , its set of edges E G , its set of production P G , or one of its sets of connection instructions C i G . For a grammar G, we will call the morphisms from EDNCE its assigning functions.
Given a multi-edNCE grammar G, a full subgrammar of G is a multi-edNCE grammar H, such that X H ⊆ X G , for each component of G and each assigning function of H is the restriction of the corresponding assigning function of G to the components of H. We will denote this with H ⊆ G.
We will say that x is an element of a multi-edNCE grammar G and denote it with x ∈ G, if x ∈ X G for some X ∈ {V, E, P, C i }. In other words, x is some vertex, edge, production or connection instruction of G. If f : G → H is a morphism in MultiEdNCE, then we will say that f (G) is the image of f and it will refer to the full subgrammar H ⊆ H whose components are f X (X G ).
The definition which we have presented for multi-edNCE grammars is clearly a proper generalization of both multigraphs and extended multigraphs. In particular, if the set P is a singleton, then we can see a multi-edNCE grammar as an extended multigraph. If, in addition, both C 0 and C 1 are the empty set, then we get a multigraph.
Definition 5.1.5 (MultiEdNCE grammars). The category of multi-edNCE grammars over a triple of labelling alphabets A = (Σ, ∆, Γ) is the category MultiEdNCE A whose objects are tuples (G, l) with G ∈ UMultiEdNCE an unlabelled multi-edNCE grammar and l = (l V , l E , l C 0 , l C 1 , l P ) a 5-tuple of labelling functions: (the vertex labelling function) l E : E G → Γ (the edge labelling function) (the in-connection instruction labelling function) (the out-connection instruction labelling function) l P : P G → Σ − ∆ (the production labelling function) A morphism between two multi-edNCE grammars f : (G, l) → (H, l ) is a morphism f : G → H of UMultiEdNCE, which in addition respects the labelling, that is the following diagrams commute: If the triple of labelling alphabets A = (Σ, ∆, Γ) is clear from the context, then we will simply refer to this category as MultiEdNCE.
The above definition of labelled multi-edNCE grammars is a generalisation of the standard edNCE grammars. What's common is that both edNCE and multi-edNCE grammars can be seen as a set of productions, where each production consists of an extended (multi)graph which has an associated nonterminal label. However, the difference is that extended multigraphs are strictly more general than extended graphs, because the former allow for parallel edges with the same label and parallel connection instructions with the same label, whereas the latter does not. It is because of this reason that multi-edNCE grammars form an adhesive category, as we show in the next theorem, but edNCE grammars form only a partially adhesive category (shown in the next subsection). Proof. We will use a proof strategy which is similar to the one used in Lemma 2.1.8, where we showed that the category of labelled multigraphs is adhesive by showing that it is isomorphic to a slice category which can easily be shown to be adhesive by the lemmas in Section 2.1.
Consider an arbitrary object (G, l) ∈ MultiEdNCE. l = (l V , l E , l C 0 , l C 1 , l P ) is a 5-tuple of labelling functions, where each l X is a morphism in Set. Thus, setting: we can see that l : S → L is a morphism in Set 5 . Next, consider the discrete category of five objects, which we shall denote with EDNCE . So, EDNCE is the same as EDNCE from Definition 5. It's easy to see that C ∼ = Set 5 . Therefore, we can see the labelling l as a morphism in C and we can see S, L as objects in C.
There's an obvious embedding E : EDNCE → EDNCE. E can be used to define a forgetful functor U : D → C, by setting: Therefore, U (G) = S and thus the labelling l can be seen as a morphism l : U (G) → L in C. The category Set has all finite limits and therefore U has a right-adjoint U R, given by the right Kan extension R(−) := Ran E (−). From the adjunction, we get a natural isomorphism Φ which provides a family of bijections: Since the labelling set L is fixed by the alphabets, we get a bijection between objects (G, l) ∈ MultiEdNCE and objects (G, Φ G,L (l)) ∈ D/R(L).
Next, for any morphism f : (G 1 , l 1 ) → (G 2 , l 2 ) ∈ MultiEdNCE we know f is a natural transformation from G 1 to G 2 which is in addition subject to the labelling restrictions of Definition 5.1.5. Any morphism f : in D/R(L) is a natural transformation from G 1 to G 2 , subject to the slice restriction, which is equivalent to the labelling restrictions of Definition 5.1.5. Therefore, Finally, it is easy to see that [EDNCE, Set]/R(L) is adhesive. As we have shown in the background chapter, this means we can do DPO rewriting in MultiEdNCE. This is the main result of this subsection, but before we conclude it, we will present two additional lemmas which will be helpful for proofs in later sections.
The first lemma will be useful when working with pushout squares in MultiEdNCE.
The second lemma characterises the matching conditions in MultiEdNCE. In the other direction, consider an arbitrary grammar G H and morphisms m : Because m and s are jointly surjective, this implies the above definition of u is unique and therefore the original square is a pushout.

No dangling connection instructions: no connection instruction
No dangling vertices: is in a production p ∈ m P (P G L − l P (P G I )).
Proof. Consider the following square: Let's assume that the above square is a pushout. From Lemma 2.1.13 we know that s and k are monomorphisms. Then, from Lemma 5.1.7 we know that s and m must be jointly surjective.
Assume the no dangling edges condition is violated, that is, there exists e ∈ E G H , e ∈ m E (E G L ) and e is incident to a vertex v ∈ m V (V G L − l V (V G I )). Joint surjectivity of m E and s E implies e ∈ s E (E G K ) and therefore v ∈ s V (V G K ). However, since G H is a pushout and v is in the image of both m V and s V , it follows v ∈ The case for connection instructions is similar. Assume the no dangling connection instructions condition is violated, that is, there exists a connection instruction c ∈ For the last case, assume the no dangling vertices condition is violated. That is, and v is in a production p ∈ m P (P G L − l P (P G I )). Joint surjectivity of m V and s V implies v ∈ s V (V G K ) and therefore p ∈ s P (P G K ). However, since G H is a pushout and p is in the image of both m P and s P , it follows p ∈ m P • l P (P G I ) which is a contradiction.
(⇐=) Let G K be the full subgrammar of G H whose components are given by , for X ∈ {V, E, P, C 0 , C 1 }. The no dangling conditions ensure that G K is a well-defined multi-edNCE grammar. Set the monomorphism s to be simply the full subgrammar inclusion of G K into G H . Set k to be set-theoretically equal to m • l. Then, clearly the square commutes and k is also a monomorphism. Then, by Lemma 5.1.7, we can complete the proof by showing that m and s are jointly surjective.
Since s is a subgrammar inclusion, then for every component X, the image of Combining this with the other monomorphism m, we get that s X and m X jointly cover: Therefore, s and m are jointly surjective.
The no dangling edges condition is the same as for the case of multigraphs.
The other two conditions are clearly very similar in spirit to the no dangling edges condition. This is a consequence of the fact that pushouts are computed componentwise in Set over some constraints imposed by the structure of our grammars.

edNCE grammars
In this subsection we will define the category of edNCE graph grammars and show that it is partially adhesive, where the ambient adhesive category is MultiEdNCE.
The edNCE graph grammars have been defined in Section 2.5 and we begin by first describing a homomorphism between two edNCE graph grammars. We will not be using any nonfinal edge labels (see Corollary 2.5.33), so our grammars can be labelled using the same triple of labelling alphabets A = (Σ, ∆, Γ) as for MultiEdNCE.
Theorem 5.1.11. edNCE is a partially adhesive category whose ambient adhesive category is MultiEdNCE.
Proof. We define a functor S : edNCE → MultiEdNCE in the following way.
Given an edNCE grammar G = (Σ, ∆, Γ, Γ, P, S), we define S(G) := H, where H is the multi-edNCE grammar whose components and assigning functions are given by: Given a morphism (f, {f p } p∈P ) between edNCE grammars G = (Σ, ∆, Γ, Γ, P, S) and G = (Σ, ∆, Γ, Γ, P , S ), we define its mapping under S to be the natural transformation φ induced by setting: The rest of the components of φ are uniquely determined from the commutativity conditions the natural transformation has to satisfy. Nevertheless, we provide them for completeness: It's easy to check that the functor S as defined is full and faithful. Finally, we have to show that S preserves monomorphisms. A morphism (f, {f p } p∈P ) in edNCE is a mono iff f and each f p are injective functions. Then, its mapping under S is a natural transformation φ, such that all of its components φ X are also injective functions, which are precisely the monos in MultiEdNCE.
Given a grammar homomorphism f between two edNCE grammars G 1 and G 2 , if v is some vertex in (the RHS of) a production p ∈ P 1 , then through abuse of notation we will use f (v) to refer to the vertex f p (v). This shouldn't lead to confusion, as each vertex v of G 1 is in a unique production and we can clearly differentiate between vertices of a grammar and the productions of a grammar. In that sense, we may think of the functions f p as restrictions of f to the extended graph rhs(p).
Following the example from Section 2.2, we will characterise the partial adhesive conditions of edNCE which allow us to do DPO rewriting in the same way as in

MultiEdNCE.
We begin by introducing a lemma which will help us with some of the remaining proofs. The lemma shows that the functor S : edNCE → MultiEdNCE is essentially surjective.
Lemma 5.1.12. For any multi-edNCE grammar G ∈ MultiEdNCE, such that G does not have any parallel edges, parallel connection instructions or self-loops, there exists an edNCE grammar H ∈ edNCE, such that S(H) is isomorphic to G.
Proof. Let the components and assigning functions of G be described as in Definition 5.1.5. For every production p ∈ P G , we define a production Y p → (D p , C p ) of H by setting: E Dp := {(s(e), l E (e), t(e))| e ∈ E G , p E (e) = p} Then, the set of productions of H is given by {Y p → (D p , C p ) | p ∈ P G }. Note, that because G does not contain any self-loops, this implies that H is a well-defined grammar (in particular, the RHS of every production is a well-defined graph). Also, note that the definition of edNCE grammar requires the set of productions to have the above form, that is, every element must be of the form Y → (D, C), where Y is a nonterminal label and (D, C) is an extended graph. Now, consider the grammar K := S(H). It is easy to see that V K = V G . Because G does not contain parallel connection instructions or parallel edges, it follows that and that all assigning functions of K, except for p V and p E are exactly the same as those of G. However, observe that P G and P K are not necessarily the same, but isomorphic. In particular, every element of P K is of the form X → (D, C), whereas the elements of P G might be arbitrary. However, there is an obvious isomorphism i : P G → P K which is simply: and therefore K and G are isomorphic as required.
Remark 5.1.13. Combining the above lemma with Theorem 5.1.11 implies that the embedding functor S establishes a categorical equivalence between the category edNCE and the full subcategory of MultiEdNCE whose objects do not contain self-loops, parallel edges or parallel connection instructions. However, this functor does not establish an isomorphism between these two categories, because of the reason mentioned in the proof above -the elements of the set of productions of edNCE grammars must be of a specific form, whereas those of multi-edNCE grammars do not. Of course, this detail is irrelevant for practical purposes, but we mention it in order to stay formal.
Next, we characterise the S-spans in edNCE.
S-span iff the following conditions hold: ParEdges: For any vertices v, w ∈ G I , if there exist edges (f (v), α, f (w)) ∈ G K and (g(v), α, g(w)) ∈ G R then there exists an edge (v, α, w) ∈ G I .
ParCI: For any vertex v ∈ G I , if there exist connection instructions (σ, α, β, f (v), d) ∈ G K and (σ, α, β, g(v), d) ∈ G R , then there exists a connection instruction (σ, α, β, v, d) ∈ Proof. In the first direction, let's assume that the above conditions hold. Then, consider the pushout of the span S(G K ) Next, let's consider parallel connection instructions. The proof is fully analogous to the case for edges -G K and G R do not have parallel connection instructions. Therefore if G M has a pair of parallel connection instructions, then their associated vertex must be identified by the morphisms f and g. In other words, a pair of parallel connection instructions in G M may only be established if G R contains a connection instruction (σ, α, β, g(v), d) and G K contains a connection instruction (σ, α, β, f (v), d), where v ∈ G I . But then, the ParCI condition requires the connection instruction (σ, α, β, v, d) ∈ G I and thus the pushout would establish exactly one connection instruction with label (σ, α, β) and direction d whose To complete the proof in this direction, we need to show G M does not contain self-loops. Neither G R , nor G K contain self-loops. The pushout is computed by taking their disjoint union and then identifying certain vertices, edges, connection instructions and productions between G R and G K as being the same. Taking their disjoint union clearly cannot result in self-loops. A self-loop can only be established if two vertices v, w from G R (G K ) connected by an edge (v, α, w) are identified as the same vertex in G K (G R ), via the morphism f (g). However this is impossible because both f and g are monomorphisms.
In the other direction, let's assume that we are given an S-span. If the ParEdges condition is violated, then the S-pushout in MultiEdNCE results in a grammar S(G M ) which contains a pair of parallel edges, thus G M is not an object in edNCE which is a contradiction. Similarly, if the ParCI condition is violated, then the Spushout in MultiEdNCE results in a grammar with a pair of parallel connection instructions and we get a contradiction.
Next, we characterize the S-matchings in edNCE. It turns out that an S-pushout complement in edNCE exists when the same matching conditions are satisfied as in MultiEdNCE as we can see in the following lemma. Therefore, since S(G H ) does not contain parallel edges, parallel connection instructions or self-loops, then neither does G K . Using Lemma 5.1.12, we may assume, without loss of generality, that G K is in the image of S and therefore from the fullness of S, it follows that s and k are also in its image. Therefore, the reflected pushout square is an S-pushout. Proof. Let the following DPO diagram describe the rewrite, it it exists: First, let's assume that the DPO rewrite is well-defined. Now, let's assume for contradiction that condition CI is violated, that is, there's a vertex v ∈ G I , connection instructions (V, α, β, m•l(v), d) ∈ G H and (V, α, β, r(v), d) ∈ G R , but no connection instruction (V, α, β, l(v), d) ∈ G L . The left square is a Spushout square and therefore there exists a connection instruction (V, α, β, k(v), d) ∈ G K . Because (V, α, β, l(v), d) ∈ G L this implies (V, α, β, v, d) ∈ G I . But then, applying Lemma 5.1.14 to the right pushout square yields a contradiction with the ParCI condition.
For the other condition, the proof is fully analogous. Let's assume for contradiction that condition Edges is violated that is, there are vertices v, w ∈ G I and edges (m • l(v), α, m • l(w)) ∈ G H and (r(v), α, r(w)) ∈ G R , but there exists no edge (l(v), α, l(w)) ∈ G L . The left square is a S-pushout square and therefore there exists an edge (k(v), α, k(w)) ∈ G K . Because (l(v), α, l(w)) ∈ G L this implies (v, α, w) ∈ G I .
But then, applying Lemma 5.1.14 to the right pushout square yields a contradiction with the Edges condition. This completes the proof in one direction.
In the other direction, we know that m is an S-matching and therefore the left pushout square is an S-pushout. So, we need to show that the right square exists and is an S-pushout. We shall show this by using Lemma 5.1.14.
Let's assume condition CI is satisfied. We shall show that condition ParCI is satisfied for the span in the right square. Let's assume for contradiction that is not the case. Thus, there exists vertex v ∈ G I and connection instructions (V, α, β, k(v), d) ∈ G K and (V, α, β, r(v), d) ∈ G R , but there exists no connection instruction (V, α, β, v, d) ∈ G I . Since the left square is an S-pushout, this implies there must be a connection instruction (V, α, β, m • l(v), d) ∈ G H . Then, condition CI implies there exists a connection instruction (V, α, β, l(v), d) ∈ G L and now we get a contradiction with Lemma 5.1.14 when applied to the left pushout square.
Next, let's assume condition Edges is satisfied. The proof is again fully analogous to the case for connection instructions. We shall show that condition ParEdges is satisfied for the span in the right square. Let's assume for contradiction that is not the case. Thus, there exist vertices v, w ∈ G I and edges (k(v), α, k(w)) ∈ G K and (r(v), α, r(w)) ∈ G R , but there exists no edge (v, α, w) ∈ G I . Since the left square is an S-pushout, this implies there must be an edge (m • l(v), α, m • l(w)) ∈ G H . Then, condition Edges implies there exists an edge (l(v), α, l(w)) ∈ G L and now we get a contradiction with Lemma 5.1.14 when applied to the left pushout square.
We will refer to the two conditions from this theorem, Edges and CI, as the partial adhesive conditions which we will make use of in later sections of this chapter.
Note, that the partial adhesive conditions alone do not guarantee the existence of a DPO rewrite. For this to be the case, we also need to combine them with the no dangling conditions, which we have also described.
In summary, we have shown that edNCE graph grammars form a partial adhesive category and we have fully characterised the conditions under which DPO rewriting can be done and is well-behaved.

B-edNCE rewriting
For the rest of the chapter, we will be working with edNCE grammars from the partially adhesive category edNCE, which was described in the previous section. grammars. Since we are interested in modelling reasoning on string graphs, it will be necessary to introduce further restrictions on the rewrite rules and matchings of our grammars if we want to be able to meaningfully talk about their languages. The additional restrictions on our matchings and our rewrite rules will ensure that DPO rewriting in B-edNCE grammars behaves well with respect to the derivation process and the languages which are generated.
In Subsection 5.2.1 we will show how to rewrite extended graphs, such that the rewrites commute with graph substitution. Graph substitution is the mechanism used to carry out derivations in grammars. DPO rewrites of extended graphs is how we simulate equational reasoning on a per-production basis for B-edNCE grammars. By identifying under what conditions these two operations commute we can significantly simplify the proofs in the following subsection.
In Subsection 5.2.2 we will show how to build upon the results from Subsection 5.2.1 in order to define admissible rewrites of entire B-edNCE grammars.

Extended graph rewrites and graph substitution
All of the constructions in this subsection will be in the category edNCE. We will be considering only edNCE grammars which have a single production (with identical and irrelevant production labels). As we have pointed out previously, we can see such grammars as extended graphs. For brevity and in order to avoid notational overhead, we will simply refer to these objects in edNCE as extended graphs.
We begin by showing that the substitution operation behaves well with respect to monomorphisms of extended graphs.
m is an injection, because both m 1 and m 2 are injections. It is also easy to verify that m is an extended graph homomorphism.
Next, we introduce the concept of an extended graph rewrite rule. This is just a special case of a rewrite rule in MultiEdNCE when the grammars are extended graphs, but we provide the definition for completeness. Example 5.2.3. The following is an extended graph rewrite rule: The only difference between an extended graph rewrite rule and a graph rewrite rule is that we also have to map the connection instructions appropriately. In this case, the monos are obvious as they are uniquely determined by the labels of the vertices.
Next, we introduce the notion of rewrite rule substitution which essentially works component-wise and its purpose is to provide notational convenience. Crucially, the monomorphisms l 3 and r 3 are built in a natural way by using the substituted monomorphism construction.

Definition 5.2.4 (Rewrite rule substitution). Given extended graph rewrite rules
Our next definition formalizes the notion of saturated matching on extended graphs which we will be using throughout this chapter. A saturated matching of extended graphs is a restricted form of matching (in the sense of the previous section). In addition to allowing us to perform DPO rewriting on extended graphs, these matchings will also later be used in order to rewrite edNCE grammars in an admissible way.
In particular, the saturated matching conditions ensure that DPO rewrites commute with the substitution operation on extended graphs (as shown in Theorem 5.2.9), which is the basic operation used to perform grammar derivations. This is not true for arbitrary DPO rewrites which satisfy only the matching conditions in edNCE, but not the additional requirements imposed by saturated matchings. • no edge e ∈ E H , e ∈ m(E L ) is incident to a nonterminal vertex in m(l(V I )) • m is a bijection on the connection instructions of L and H, that is, In particular, the first condition is the standard no-dangling edges condition for (extended) graphs. The third condition concerns connection instructions and is obviously stricter than the no-dangling connection instructions condition which is needed in order to ensure that the pushout complement of extended graphs exists. The additional strictness of the third condition, together with the second condition (which can be seen as imposing further restrictions on the no-dangling edges condition) guarantee that rewriting productions of grammars behave nicely with respect to the derivations of the grammar (which is based on extended graph substitution).
We can show that DPO rewrites on extended graphs preserve saturated matchings. Proof. By contradiction. Assume there exists an edge e ∈ E M , e ∈ f (E R ) such that e is incident to a vertex v ∈ f (V R − r(V I )). Because the right square is a pushout, then from the joint surjectivity of f and g, we get that e ∈ g(E K ). Since g is an (extended) graph homomorphism, it follows immediately that v ∈ g(V K ). Thus, the vertex v is in the images of both g and f and because the right square is a pushout, it follows v is also in the image of f • r = g • k, which is a contradiction. Assume there exists an edge e ∈ E M , e ∈ f (E R ), such that e is incident to a nonterminal vertex v in f (r(V I )). Let u ∈ V I be the nonterminal vertex of V I , such that f • r(u) = v. As in the previous case, we see that e ∈ g(E K ). Let e ∈ E K be the edge such that g(e ) = e and then e must be incident to the vertex k(u), since e = g(e ) is incident to v = f •r(u) = g•k(u). Now, consider the edge e = s(e ) ∈ E H . If e is in the image of m, then because the left square is a pushout, we get that e must also be in the image of m•l = s•k and we get a contradiction with the fact that e ∈ f (E R ). Thus, e ∈ E H − m(E L ). Because s is an extended graph homomorphism, it then follows that e is incident to s • k(u) = m • l(u) and we get a contradiction with the fact that m is a saturated matching (the second condition of the definition is violated).
Finally, we have to show that f is a bijection on the connection instructions of R and M . We know that f is a mono, so therefore we just have to show that f is a surjection. Assume that there exists a connection instruction c ∈ C M which is not in the image of f . The right square is a pushout, therefore f and g are jointly surjective.
Thus, c = g(c ) for some c ∈ C K . Therefore, s(c ) ∈ C H is a connection instruction of Proof. Without loss of generality, we can take isomorphic copies of all these graphs, such that all of the monos are simply subgraph inclusions. So, for simplicity, we shall assume that is the case. Also, we shall refer to the saturated matching conditions simply as matching conditions.
Moreover, e ∈ E L 3 implies e ∈ E L 1 and e ∈ E L 2 . If e ∈ E H , then the fact that e is incident to u ∈ V L 3 − V I 3 implies u ∈ V L 1 − V I 1 which contradicts the matching conditions for m 1 . If e ∈ E D , then the fact that e is incident to u ∈ V L 3 − V I 3 implies that u ∈ V L 2 − V I 2 which contradicts the matching conditions for m 2 .
Therefore, e must be a bridge, that is, an edge established by the substitution operation and is neither in E H , nor E D . Because e is incident to u ∈ V L 3 − V I 3 , there are two further cases to consider. If u ∈ V L 1 − V I 1 , then there is an edge e between u and v in E H . From the matching condition for m 1 it then follows that e ∈ E L 1 . Moreover, there must also be a connection instruction c ∈ C D , which establishes the bridge e between u and u ∈ V D . Then, from the matching condition on m 2 it follows c ∈ C L 2 and therefore e ∈ E L 3 = E L 1 [v/L 2 ] , which is a contradiction.
If u ∈ V L 2 − V I 2 , then let u ∈ V H be the other incident vertex of e. Because e is a bridge, this implies that there is a connection instruction c = (λ(u ), β, γ, u, d) ∈ C D associated to u. Then, the matching condition for m 2 implies c ∈ C L 2 . Since v is a nonterminal vertex in V I 1 and there must be an edge e ∈ E H between u and v with label β and direction d, then it follows from the matching condition of m 1 that The previous lemma shows that the substitution operation behaves well with respect to saturated matchings. The next lemma shows that the substitution operation preserves S-pushout squares, when some of the morphisms are saturated matchings.
Commutativity follows easily by construction of the x 3 monos and the commutativity of the original two pushout squares. To finish the proof, we need to show that k 3 and m 3 are jointly surjective (Lemma 5.1.7) and that the third square (the substituted one) satisfies the ParCI and ParEdges conditions from Lemma 5.1.14. For simplicity and without loss of generality, we shall assume X 1 and X 2 are disjoint and that x 1 and x 2 are subgraph inclusions, where X ∈ {I, L, K, H}, x ∈ {i, l, m, k}.
We will first show that k 3 and m 3 are jointly surjective. Now, let's consider an arbitrary vertex u ∈ H 3 := H 1 [v/H 2 ]. By definition of substitution, u ∈ H 1 or u ∈ H 2 .
If u ∈ H 1 , then the joint surjectivity of k 3 and m 3 follows from the joint surjectivity of k 1 and m 1 . The other case follows in the same way and therefore k 3 and m 3 are jointly surjective on vertices.
Taking an arbitrary edge e ∈ H 3 , there are three cases to consider. If e ∈ H 1 or e ∈ H 2 , then the case follows using exactly the same argument as those for vertices. The remaining case is when e is a bridge established by the substitution operation. Let the two endpoints of e be vertices w 1 ∈ V H 1 and w 2 ∈ V H 2 . Then, there must exist an edge e ∈ H 1 which is adjacent to the nonterminal vertex v, and there must exist a connection instruction c ∈ H 2 which is compatible with e , that is, where α is the label of e , β is the label of e and d is the direction w 1 is connected to v. m 2 is a saturated matching and then the third matching condition implies c ∈ L 2 . m 1 is also a saturated matching and then the second matching condition implies e ∈ L 1 . Thus, by definition of substitution, it follows e ∈ L 1 [v/L 2 ] =: L 3 . Therefore, k 3 and m 3 are jointly surjective on edges as well.
From Lemma 5.2.7, it follows that m 3 is a saturated matching with respect to the depicted square and therefore, according to the third matching condition, m 3 is a bijection on connection instructions which immediately implies joint surjectivity of m 3 and k 3 on connection instructions. Next, let's consider the ParCI condition for the third square. From the left pushout square, we know that C L 1 = C H 1 , because m 1 is a saturated matching. Since the square is a S-pushout square, it follows that Similarly, from the second pushout square we get C K 2 = C I 2 . Next, observe that any edge e ∈ K 1 which is incident to v, must also be in I 1 , that is e ∈ I 1 , because otherwise H 1 would contain an edge incident to v which is not in the image of m 1 and therefore the second condition of saturated matchings is violated. Therefore, the vertex v has the same set of adjacent edges (and vertices) in both K 1 and I 1 . Combining this with the fact that C K 1 = C I 1 and C K 2 = C I 2 means that I 1 [v/I 2 ] =: have the same connection instructions. This then immediately implies that the ParCI condition is satisfied for the third square.
Finally, let's consider the ParEdges condition. Take an arbitrary edge e = (w 1 , γ, w 2 ) ∈ K 3 , where w 1 , w 2 ∈ I 3 . If w 1 , w 2 ∈ I 1 , then e ∈ K 1 and if e ∈ L 1 , the ParEdges condition for the first pushout square implies e ∈ I 1 and therefore e ∈ I 3 . So, in this case, the ParEdges condition is satisfied. Similarly, if w 1 , w 2 ∈ I 2 , the ParEdges condition is again satisfied using the same argument.
If w 1 ∈ I 1 , but w 2 ∈ I 2 , then e is a bridge established by the substitution. Thus, there must be a connection instruction c = (λ(w 1 ), β, γ, w 2 , in) ∈ C K 2 = C I 2 and there must be an edge (w 1 , β, v) ∈ K 1 . As we have already pointed out, v has the same set of adjacent edges and vertices in both K 1 and I 1 . Combining this with the fact that c ∈ C I 2 means that the edge e = (w 1 , γ, w 2 ) ∈ I 3 and therefore the ParEdges condition is satisfied.
The last case is when w 1 ∈ I 2 and w 2 ∈ I 1 . This follows using a similar argument to the previous case, where we also have to change the direction of the connection instruction from in to out.
Building on the previous two lemmas, we can now show that rewriting of extended graphs commutes with the substitution operation. We will prove this in the next theorem, which is the main result of this subsection. This is crucial for establishing the admissibility properties of grammar rewriting that we require, because derivations in edNCE grammars work by repeatedly applying the substitution operation to nonterminal vertices.
In terms of diagrams, given the following two S-rewrites: Then the following diagram is also an S-rewrite:

Admissible B-edNCE grammar rewriting
In the previous subsection we showed how to rewrite extended graphs in a way which respects graph substitutions. Every production of a B-edNCE grammar is simply an extended graph which also has an associated nonterminal label. We will use the results from the previous subsection for rewriting B-edNCE grammars locally, that is, on a per-production basis. In this subsection, we will describe the rest of the conditions which we need in order to rewrite B-edNCE grammars in a way which respects their concrete derivations. In general, a rewrite rule in edNCE is simply a span of monomorphisms G L l ← − However, in the absence of additional structure between these grammars, it is very difficult to relate their languages in any way. So, we begin by introducing extra structure which would then allow us to relate their languages by considering parallel derivations in all three grammars.
where m p i is the restriction of m to the extended graph rhs(p i ). We will refer to s 2 as the induced embedding of s 1 into G 2 over m.
Proof. For each production p i of G 1 , we know there exists a corresponding production m(p i ) of G 2 by definition of grammar morphism. The same definition then also implies that production m(p i−1 ) will create nonterminal vertex m(v i ) in G 2 , where nonterminal vertex v i is created by production p i−1 of G 1 . Thus, the derivation sequence s 2 is well-defined.
Clearly, m 0 is a mono and observe that each m p i is also a mono on extended graphs (because it is simply the restriction of m which is a mono). Then, by inductively applying Lemma 5.2.1, it follows that each m i is a mono.
Note that in the above definition we implicitly assume that m acts on disjoint and isomorphic production copies of the productions for simplicity of the definition.
Thus, when there exists a mono between grammars G 1 and G 2 , then for each concrete derivation s 1 in G 1 , we can consider a corresponding derivation s 2 (not necessarily concrete) in G 2 where each extended graph in s 1 can be injectively mapped into a corresponding extended graph in s 2 . In particular, this means that the sentential forms of G 1 can be injectively mapped into corresponding sentential forms of G 2 . → G R , a (concrete) pattern instantiation is a triple of (concrete) derivation sequences of the following form: Therefore, by performing parallel derivations, a B-edNCE pattern can be used to specify infinitely many rewrite rules between concrete graphs. In this sense, a B-edNCE pattern may be seen as representing an equational schema between families of graphs.
Example 5.2.14. Consider the B-edNCE pattern from Example 5.2.11. Every parallel instantiation of length n gives us a graph rewrite rule which may be used for rewriting. For example, a derivation of length 3 results in the following graph rewrite rule: where the concrete graphs form a span which is a graph rewrite rule. The particular morphisms for the span are induced from the B-edNCE rewrite rule, as explained in the previous definition. This particular rule rewrites K 3 to K 1,3 by deleting one edge.
In Section 5.1, we showed how to compute pushout complements and we identified the matching conditions under which they exist. However, arbitrary grammar matchings may result in grammars whose induced languages are difficult to reason about using the B-edNCE patterns that we have. So, we shall introduce saturated grammar matchings which are special kinds of grammar matchings. We will later prove that by restricting ourselves to saturated grammar matchings, we will be able to rewrite entire B-edNCE grammars using a B-edNCE pattern in a way which allows us to relate concrete derivations using the graph rewrite rules induced by the pattern. Proof. Let the root of Y be n and let's assume it has label p. If n is also the root of T , then lhs(p) = S by the initiality condition. Otherwise, consider the predecessor of n which we shall call k. If k is not a matched node, then it follows from the nonterminal covering condition that lhs(p) = S. If k is a matched node, then the edge between k and n is not matched as otherwise we would violate the maximality assumption for Y . Then, it follows lhs(p) = S by the nonterminal covering condition. Therefore, in all cases, lhs(p) = S.
From this, by using the production branching condition, we get that there exists p ∈ G L with lhs(p ) = S and m(p ) = p. The root of Y is then a node with label p .
Using an inductive argument, we can explain how to construct the rest of Y . Let k be a node in Y for which we have already constructed its isomorphic counterpart k in Y . Let h be any child of k which is also in Y and let its label be p. Then, h is a matched node and therefore we can construct a node h in Y with label p ∈ G L , such that m(p ) = p, as required. The parent edge e of h is a matched edge, therefore it identifies a nonterminal vertex x in the image of m. Thus, we can construct an edge e from k to h in Y which identifies the pre-image of x.
What remains to be shown is that the tree Y is concrete. We already know that the root of Y is an initial production of G L , so the proposition will follow if we prove that every node in Y has as many children as it has nonterminal vertices in its associated production in G L . This is equivalent to proving that every node in  the maximal subtree consisting of matched nodes and edges is coloured in red. That is because only these productions are matched from the B-edNCE pattern. Also, it's easy to see that the corresponding derivation tree consisting of only the red nodes and edges is concrete for the B-edNCE pattern.
We have seen that B-edNCE patterns are useful for relating the derivations between a triple of grammars. However, when we rewrite a target grammar, we wish to relate its language to the language of the result of the rewrite. In order to do this, we will introduce a notion which is similar to that of B-edNCE pattern, but instead it is defined over a pair of grammars.
where F is the bijection between the productions and nonterminal vertices of the correspondence.
Clearly a B-edNCE pattern and a B-edNCE correspondence are very closely related. In fact, every B-edNCE pattern induces a B-edNCE correspondence by choosing any two of its grammars (and defining the necessary bijection appropriately). Our next lemma shows the interplay between B-edNCE patterns, saturated matchings and B-edNCE correspondences.
and the bijection G between the nonterminal vertices of G H and G M is given by: Proof. An S-rewrite in edNCE does not modify the initial nonterminal label of the grammar. Therefore, both grammars G H and G M have the same initial nonterminal. The fact that there is a bijection between the productions of G H and G M follows after recognizing that only the bodies of the productions in G H are rewritten. In particular, notice that each production p ∈ G L (G R ) is in the image of l (r). Therefore, no productions are added, nor removed when performing the rewrite. This means that the definition of F above is complete (in the sense that it is totally defined) and checking that it is a label-preserving bijection follows immediately.
Showing that G is a bijection on nonterminal vertices follows by a completely We also have to show in addition that G M is a B-edNCE grammar. This follows immediately after recognizing that a rule B p from a B-edNCE pattern cannot add edges between nonterminal vertices, nor can it add connection instructions of the form (X, α, β, x, d), where X is a nonterminal label, as this violates the definition of B-edNCE grammars.
As the above lemma shows, when we are doing grammar rewrites over saturated matchings, then we get a B-edNCE correspondence. In particular, the bijections F and G relate nonterminal vertices and productions from G H to those of G M . If x (p) is a nonterminal vertex (production) of G H and x (p ) is a nonterminal vertex (production) of G M , such that G(x) = x (F (p) = p ), then we shall say that x and x (p and p ) are corresponding nonterminal vertices (productions). In particular, if in the above lemma all morphisms are subgraph inclusions, then the two bijections are simply the identity function.
condition which is satisfied for m. Finally, the Nonterminal covering condition is satisfied for f , because G L and G R use the same nonterminal labels, each nonterminal , where x is the corresponding nonterminal vertex of x in G R , and because the Nonterminal covering condition is satisfied for m.
A B-edNCE correspondence between two grammars G 1 and G 2 allows us to pair up concrete graphs from L(G 1 ) and L(G 2 ). Our final definition from this section is the notion of an admissible B-edNCE correspondence. In short, an admissible correspondence with respect to a set of rewrite rules R allows us to rewrite any graph from L(G 1 ) into its corresponding graph from L(G 2 ) using some rewrite rules from R. Essentially, the next definition formalizes the notion of a sound transformation between two grammars. Proof. From Lemma 5.2.22, we know that (G H , G H ) is indeed a B-edNCE correspondence. Thus, for every concrete derivation tree T of G H , an isomorphic concrete derivation tree T exists for G H . However, the yield of T and the yield of T may differ. In particular, any subtree consisting entirely of non-matched nodes in T has the same yield as its corresponding subtree in T . But a subtree consisting of matched nodes in T may have a different yield compared to its corresponding tree in T .
In the base case, if we consider a single matched node u in T and its corresponding node u in T , then if the label of u is a production p of G H , then the label of u is a production p obtained by performing the rewrite rhs(p) Bp l ,mp rhs(p ), where p l ∈ G L is the production of G L such that m(p l ) = p and m p is the restriction of m to rhs(p). Thus, by repeatedly applying Theorem 5.2.9, we know there exist m and R, such that yield(Y ) R,m yield(Y ), for any subtree Y of T consisting of matched nodes and edges and Y is its corresponding tree in T . If we choose Y to be maximal with respect to matched nodes and edges, then by Lemma 5.2.18 R would be in L(B). This means R is a standard DPO rewrite rule on terminal graphs. Then, if Y i are the maximal subtrees of T consisting of matched nodes and edges and Y i are their corresponding counterparts in T , we can rewrite yield(T ) s yield(T ) using a sequence of rewrite rules s consisting of rules R i obtained as already explained (where the matchings extend trivially). The rules R i can be applied in any order, or in fact all at the same time in parallel, as they are matched on disjoint parts of the graph yield(T ).
What remains to be shown is that the no-dangling edges condition for DPO rewriting on graphs is satisfied when applying each rewrite rule R i to the larger graph yield(T ) and we also need to explain how to extend the matchings to the larger graph yield(T ) from what we have already described.
Note, that for any maximal matched subtree Y of T , yield(Y ) is in general a sentential form of G H . As already explained, we can rewrite such a sentential form to the corresponding sentential form yield(Y ) of G H using a graph rewrite rule R at a matching m , that is, yield(Y ) R,m yield(Y ). However, in yield(T ) some of the nonterminal vertices of yield(Y ) may be expanded, and, in addition, yield(Y ) may itself be substituted for another nonterminal vertex of another sentential form. In both cases, we can extend the match m to yield(T ) triviallym maps a terminal graph to a terminal graph of yield(Y ), which is unmodified after all substitutions in yield(T ), therefore the extended matching is the same as m , where only the codomain is changed. Because that matching is injective, we need to show the standard nodangling edges condition for graphs is satisfied.
Observe, that the root of Y is labelled by the initial nonterminal label of G L . Thus, by assumption, this production has no connection instructions in G L and therefore neither does the corresponding production in G H (follows from the production saturation condition The same derivation tree may be used for grammar G M (because the two grammars form a B-edNCE correspondence) and its yield is the graph M, given by:

M :
Then, from the main theorem in this section, we know that we can rewrite H m,s M , where both the matching m and the rewrite rule s are induced from the B-edNCE pattern used for the rewrite in combination with the derivation tree Y . In particular, in order to obtain the rewrite rule s, we simply take all the maximal matched subtrees (in this case it is only one) whose yields are then concrete graph rewrite rules which we need to apply. In this case, s may be constructed by the parallel derivation from Example 5.2.14, as this is the yield of the maximal matched subtree of Y when evaluated at the pattern.
In summary, we have shown how to rewrite B-edNCE grammars using B-edNCE rewrite patterns in such a way that we can systematically relate their languages using DPO rewrites induced by the rewrite patterns. In the following sections, we will build upon these results by showing how to extend them to B-ESG grammars, so that we may apply these techniques to the languages of string graphs (and thus string diagrams) we are interested in. Then we will see that the notion of admissibility we have introduced in this section translates into sound rewrites of the string diagram families we are representing.

B-ESG rewrite rules
In Chapter 4 we introduced B-ESG grammars which generate languages of string graphs and which have some important decidability properties. We can use a single B-ESG grammar to represent a single family of string graphs. However, we still have not described how to represent equational schemas between families of string graphs. This is the primary contribution of this section.
We begin by introducing two auxiliary definitions.
Definition 5.3.1 (Production input/output/isolated vertex). Given a B-ESG grammar B, we say that a wire-vertex w is a production input if its production in-degree is zero. w is a production output if its production out-degree is zero. w is a production isolated wire-vertex if its production in-degree and production out-degree are both zero.
• is neighbourhood preserving • is context-consistent • contains no useless connection instructions • is reduced Moreover, we will say that B is in proper B-ESG normal form, if B is in B-ESG normal form and also G contains no production isolated wire-vertices.
Next, we introduce the notion of B-ESG rewrite pattern which extends the notion of B-edNCE correspondence to B-ESG grammars. As such, we can use B-ESG rewrite patterns to relate the languages of two B-ESG grammars. IO: There is a label-preserving bijection between the production inputs (outputs) in p and the production inputs (outputs) in p .
In the above definition, grammars G 1 and G 2 form a B-edNCE correspondence and therefore we may perform parallel derivation sequences on both grammars G 1 and G 2 in the same way as in the previous section, which would generate a pair of encoded string graphs. If we follow this by a decoding, then we would get a pair of string graphs. This is made precise by the next definition.  T ) and B 2 = (G 2 , T ) a B-ESG pattern instantiation is given by an instantiation for (G 1 , G 2 ), followed by a decoding: where K is the bijection between the productions and nonterminal vertices of the In other words, we use an identical derivation sequence in the two B-edNCE grammars to get two encoded string graphs, which are then uniquely decoded using the rewrite rules of T . This example is particularly interesting, because it contains the essential graph data of the 'Y-∆ rule' from electrical circuits [14] as well as the local complementation rule for which we mentioned in the introduction that it is very important for measurement-based quantum computation [50,20]. Every parallel instantiation of length n thus gives a pair of string graphs where their inputs and outputs are in 1-1 correspondence. For example, a parallel derivation of length 3 (not counting decoding), gives us: Observe, that after each derivation step, the inputs/outputs and the nonterminal vertices are in bijection. In the above definition, we are using the same symbol to refer to both a B-ESG morphism and also its underlying edNCE morphism. We do this for simplicity, because the two are exactly the same. It will always be clear from context to which notion we are referring to. It is also obvious that, for any choice of T , B-ESG T is isomorphic to the full subcategory of edNCE whose objects satisfy the B-ESG conditions. Also, for brevity, if we denote a B-ESG grammar as B X , then its underlying edNCE grammar will be denoted G X , so that B X = (G X , T ). From now on, we also assume that the decoding system T is fixed for all B-ESG grammars.
We proceed by defining B-ESG rewrite rules. A B-ESG rewrite rule is simply a B-edNCE rewrite pattern which has been extended to B-ESG grammars. B-ESG rewrite rules, can be used to relate the languages of three B-ESG grammars and they are used in order to generate a language consisting of string graph rewrite rules. IO2: For every wire-vertex w ∈ p I , l(w) and r(w) are both a production input (output) in p L and p R respectively.
Moreover, G I is in B-ESG normal form and grammars G L , G R are both in proper B-ESG normal form.
B-ESG rewrite rules and B-ESG rewrite patterns are very tightly related. The next two lemmas show that they are interchargable -we can get a B-ESG rewrite rule from a B-ESG rewrite pattern and vice-versa. So, a natural question to ask is why do we introduce two different notions which are recoverable from one another. This is because a B-ESG rewrite rule explicitly generates a language consisting of string graph rewrite rules (as we shall prove) while a B-ESG rewrite pattern is useful for describing the relationship between grammar rewrites (in this sense it is similar to a B-edNCE correspondence).
However, note that the analogous notions -B-edNCE patterns and B-edNCE correspondences -are not interchargable. The reason why this is the case is because string graph rewrite rules have a natural boundary -it simply consists of all of the inputs and outputs which must be the same in both the left-hand side and the righthand side of each rule (cf. Section 2.3). However, no such analogous notion exists for arbitrary graphs.
Proof. The only property which isn't immediately obvious is the IO property from the definition of B-ESG rewrite pattern. However, this follows by combining properties IO1 and IO2 from the definition of B-ESG rewrite rule. In particular, the bijection can be defined by identifying l(w) with r(w) for each wire-vertex w ∈ G I . Condition IO2 ensures l(w) and r(w) are both production inputs (outputs) and condition IO1 ensures that every production input (output) in G L and G R is covered by l and r in this way. Proof. The triple (G L , G I , G R ) has to be a B-edNCE pattern. This means that if G L and G R have n productions, then G I must have n productions as well. Moreover → G R is a span and l and r establish the bijective correspondence between the productions of the three grammars. So, if the productions of G L are {X i → (D i , C i )} i∈I , then we can assume without loss of generality that the productions of G I are given by {X i → (D i , C i )} i∈I . Let's consider a triple of corresponding productions p L = X i → (D i , C i ), p I = X i → (D i , C i ) and p R = X i → (D i , C i ) in G L , G I and G R respectively. From the B-edNCE pattern requirement, it follows that the nonterminal because all productions have one wire-vertex and one nonterminal vertex. This rewrite rule will rewrite a complete string graph (where all node-vertices have one output) to a star string graph (where all node-vertices have one output).
Every parallel instantiation of length n thus gives us a string graph rewrite rule which may be used for rewriting. For example, a derivation of length 3 (not counting decoding) gives us: where the concrete string graphs form a span which is a string graph rewrite rule. The particular morphisms for the span are induced from the B-ESG rewrite rule, as explained in Definition 5.3.12, which we shall soon provide.
Before we introduce our notion of instantiation for B-ESG rewrite rule, it is useful to present the next lemma. It shows that if one encoded string graph embeds into another, then so do their decoded counterparts. K . We will refer to this monomorphism as the decoded embedding of H into K .
Proof. We can define m by induction on the number of encoding edges of H.
If H contains no encoding edges, then m = m. Otherwise, to construct a mono for a single decoding step by replacing some edge e ∈ H, consider the following.
Since m : H → K is a monomorphism, then there exists an edge m(e) ∈ K which is also an encoding edge. Then, m acts exactly as m on all vertices and edges, except on the newly introduced ones after performing the decoding H =⇒ T e H and K =⇒ T m(e) K , where it is undefined. However, by definition, the decoding process will introduce exactly the same graph (up to isomorphism) in both H and K , so m can be trivially extended.
Next, we define how to instantiate B-ESG rewrite rules. This is a simple generalisation of B-edNCE pattern instantiations.  The main result in this section is to show that every B-ESG rewrite rule induces a language consisting of string graph rewrite rules. From this it easily follows that every pair of corresponding string graphs in a B-ESG rewrite pattern have corresponding inputs and outputs. Therefore, B-ESG rewrite patterns correctly represent equational schemas between families of string diagrams. We have shown B-ESG rewrite patterns and B-ESG rewrite rules are interchargable, but in the last section we will mostly be working with B-ESG rewrite rules. The reason is simple -B-ESG rewrite rules can be readily used for rewriting, whereas B-ESG rewrite patterns cannot (they have to be converted to a B-ESG rewrite rule first).
We will prove the main result by induction. In particular, we will show that every instantiation (not necessarily concrete) is an ESG-form rewrite rule, which is a straightforward generalisation of string graph rewrite rule (cf. Definition 2.3.7). So, in the above definition, we see that if our graphs do not contain any nonterminal vertices, then we get a rewrite rule between encoded string graphs. Furthermore, it is easy to see that a string graph rewrite rule is simply an ESG rewrite rule, where all three graphs contain no encoding edges. Lemma 5.3.14. Given a B-ESG rewrite rule, every parallel instantiation: We know that all of the grammars are neighbourhood-preserving, this means that the in-degree (out-degree) of vertices in any sentential form cannot decrease as we expand nonterminal vertices. Moreover, condition W2 from Definition 4.2.12 implies that the in-degree (out-degree) of any wire-vertex cannot increase after applying a production. Therefore, the inputs, outputs and isolated wire-vertices are preserved when applying productions to our sentential forms. Therefore, to prove the proposition, we simply have to show that the newly introduced wire-vertices in H n , H n , H n satisfy the required conditions.
We also know that all three grammars are context-consistent and they contain no useless connection instructions. Therefore, if some wire-vertex has production indegree (out-degree) n, then its in-degree (out-degree) in any sentential form of the grammar will also be n, after applying the production which contains it. This fact is crucial for the proof of this lemma.
Property P1 follows for the span H n ln ← − H n rn − → H n from the induction hypothesis and because neither l(p n ), nor r(p n ) contain production isolated wire-vertices.
Next, we will show that properties P2 and P3 hold for inputs (the case for outputs follows by symmetry). This follows by combining the induction hypothesis with conditions IO1 and IO2 which are satisfied by the productions p n , r(p n ), l(p n ).
Finally, property P4 holds, because the bijections between the inputs/outputs are defined in terms of the embedding morphisms l n , r n , so they hold by construction.
Proof. This follows immediately from the previous lemma after recognising that in a concrete derivation there are no nonterminal vertices left.
The main result in this section then follows as a simple consequence of the above results. Proof. Consider a concrete instantiation:  11, we see that the decoded embedding simply extends the monomorphisms, so l F (r F ) acts in the same way when restricted to l n (r n ). The decoding process by definition does not establish any new inputs, nor outputs and therefore,

B-ESG rewriting
We have shown how to represent families of string diagrams using B-ESG grammars. We have also shown how to represent equational schemas using B-ESG rewrite patterns. These rewrite patterns induce B-ESG rewrite rules which may be used for rewriting other B-ESG grammars. In the final section of this thesis, we will combine the results of Section 5.3 and Section 5.2 to show how we can rewrite B-ESG grammars in an admissible way. This would then show that our framework correctly represents reasoning with infinite families of string diagrams, even when we are rewriting them using equational schemas of infinite families of string diagrams.
We begin by introducing the most central definition in this chapter which combines most of our previous constructions. We will be referring to it multiple times before the end of the chapter. It formally defines what we mean by rewriting a B-ESG grammar.
In particular, we use a B-ESG rewrite rule and a saturated grammar matching which also satisfies the partially adhesive conditions to get an S-rewrite.  where the equational schema (B) was used, given by: where in both of the above examples, K n is the complete string diagram on n white node-vertices, S n is the star string diagram on n node-vertices.

Rewrites preserve B-ESG structure
A B-ESG grammar has a lot of structure, so we need to prove that the encoded B-edNCE grammar which results from the rewrite satisfies multiple conditions. Some of the lemmas in this section, like the ones which establish normal forms, are not strictly required for this subsection, but they make the proofs considerably easier. → G L . Then, we know from the Production saturation condition, and in particular the fact that f also acts as a saturated extended graph matching, that x and x will have the same connection instructions. The same condition also implies that the edge neighbourhoods of x and x will be the same. Therefore x and x have the same context.
For the second property, observe that x can only be adjacent to boundary vertices or to vertices outside of the image of f (that is the standard no-dangling edges condition). Therefore, its edge-neighbourhood is exactly the same as the edgeneighbourhood of x . Next, consider an arbitrary connection instruction associated to x. Such a connection instruction is not in the image of f and therefore it must have been preserved by the rewrite, so x has the same connection instruction. Therefore, x and x have the same context. Proof. S is the initial nonterminal label in G L and G R , therefore there exists at least one production p with label S in both of these grammars. By assumption, p must have empty connection instructions. Therefore, from the Production saturation condition which is satisfied for the saturated matching m, it follows m(p) will also have empty connection instructions in G H . Therefore, both G H and G R contain at least one production with label S and empty connection instructions. This means that any nonterminal vertex x with label S in G H or G R must have empty context.
Otherwise, we get a contradiction with the fact that G H or G R is neighbourhoodpreserving, context-consistent and contain no useless connection instructions. Then, from the previous lemma it follows that each nonterminal vertex with label S in G M must also have empty context. The next lemma is very powerful, as it follows as a corollary that several normal forms for our rewritten grammar are satisfied. The proof is done by induction over the length of the derivations which produce the sentential forms. In particular, the strengthened statements (compared to what is needed for the normal forms) make the proof considerably simpler compared to what is required by proving each normal form separately. 2. expanding any nonterminal vertex x in any sentential form of G M will use all of its incident edges to create bridges.
Proof. Let the context functions for G R and G H be η R and η H respectively. Consider an arbitrary nonterminal label X. If X = S, then from Corollary 5.4.6, it follows that each nonterminal vertex x with label S in any sentential form has empty context. So let us assume that X = S.
If X is a label which is not used in the grammar G R , then no production with label X is in the image of f and no nonterminal vertex with label X is in the image of f . Thus, the connection instructions of such productions in G M are the same as their counterparts in G H and the context of nonterminal vertices with label X in G M is the same as their counterparts in G H (the latter follows from Lemma 5.4.5).
If X is a label which is used in the grammar G R , then let's consider an arbitrary nonterminal vertex x with label X in G M . We know f is a saturated matching and therefore from the Nonterminal covering condition it follows x ∈ f (G R ). Therefore there exists a nonterminal vertex x ∈ G R , such that f (x ) = x. From Lemma 5.4.5, we know the context of x in G M is the same as the context of x in G R . From the Production branching and the Production saturation conditions it follows that every production with label X in G M has the same connection instructions as its pre-image in G R . Therefore, all nonterminal vertices with label X in G M have the same context as their pre-images in G R and all productions with label X in G M also have the same connection instructions as their pre-images in G R .
Therefore, in all cases, a nonterminal vertex x with label X has the same context in G M as either its counterpart in G H or its pre-image in G R , depending solely on whether or not X is used in G R or not. Because both grammars G R and G H are context-consistent and contain no useless connection instructions, this means the context of x in G M is η R (X) or η H (X), if X is used in G R or not, respectively.
Similarly, every production p with label X has the same connection instructions in G M as either its counterpart in G H or its pre-image in G R , depending solely on whether or not X is used in G R or not. We will use these two facts to prove that the conclusion holds.
We will prove by induction on the length of the derivation that each connection instruction is used to establish a bridge every time a nonterminal vertex is replaced and also that all of its incident edges are also used to create bridges.
In the base case, the sentential form is just sn(U, z), where U is the initial nonterminal label for G M , which by definition is the same as the one for G H . Let's consider an arbitrary expansion sn(U, z) =⇒ z,p H, where p ∈ G M with label U . If U = S, then as already shown, p must have connection instructions as its pre-image in G R , which has empty connection instructions by assumption. If U = S, then by the Initiality condition U is not used in G R and therefore p has the same connection instructions as its corresponding production in G H , which is initial and therefore has no connection instructions. In both cases, the first proposition follows trivially and the second one also follows trivially, because sn(U, z) has no edges.
For the step case, assume that we have proved our propositions for all sentential forms sn(S, x 1 ) =⇒ x 1 ,p 1 H 1 =⇒ x 2 ,p 2 · · · =⇒ xn,pn H n , where the length of the derivation sequence is at most n. Let x n+1 ∈ H n be an arbitrary nonterminal vertex with label X and let's assume it was created by production p k . Then, from the induction hypothesis, it follows the context of x n+1 in H n is the same as the context of x n+1 in rhs(p k ), which is the body of a production in G M . If X is used in G R , then this context is η R (X) and otherwise it is η H (X), as already pointed out.
Consider the sentential form H n =⇒ x n+1 ,p n+1 H n+1 , where p n+1 is an arbitrary production with label X.
If X is a label which is not used in G R , then the context of x n+1 in H n is η H (X).
We have also shown that p n+1 must have the same connection instructions as its corresponding production in G H . Therefore, all of the connection instructions in p must be used to create bridges, because otherwise we get a contradiction with the fact that G H is context-consistent and contains no useless connection instructions.
Moreover, every edge incident to x n+1 must also be used in order to create bridges, because otherwise we get a contradiction with the fact that G H is neighbourhoodpreserving.
If X is a label which is used in G R , then the context of x n+1 in H n is η R (X).
We have also shown that p n+1 must have the same connection instructions as its pre-image in G R . Therefore, all of the connection instructions in p must be used to create bridges, because otherwise we get a contradiction with the fact that G R is context-consistent and contains no useless connection instructions. Moreover, every edge incident to x n+1 must also be used in order to create bridges, because otherwise we get a contradiction with the fact that G R is neighbourhood-preserving. Proof. The fact that G M does not contain useless connection instructions follows immediately from the first proposition of the previous lemma as its statement is clearly stronger. The second proposition of the previous lemma immediately implies that G M is neighbourhood-preserving, as it is clearly equivalent to the definition.
For context-consistency, the previous lemma implies that the context of any nonterminal vertex x with label X in a production p of G M is the same as the context of x in any sentential form of G M when x is created by an application of p. However, as we have pointed out in the proof of the previous lemma, the context of x within the grammar G M is determined solely by its label X -if X is used in G R , then its context is η R (X) and otherwise it is η H (X). Therefore, the context function is given by: Wire-consistency (cf. Definition 4.2.7) is one of the necessary properties of B-ESG grammars. The next lemma proves that the rewritten grammar is indeed wireconsistent. Proof. Let's assume that the initial nonterminal label of G L l ← − G I r − → G R is S. Assume G M is not wire-consistent. This means, there exists a production p ∈ G M which contains a nonterminal vertex x 0 ∈ rhs(p), such that x 0 has context cardinality (σ, α 0 , d) at least two, for some σ ∈ Σ, α 0 ∈ Γ, d ∈ {in, out}. Moreover, there must be a nonterminal vertex x n with label X ∈ Σ, such that x 0 Q d σ (α 0 , α n ) x n (this is the multi-step context-passing relation). It must also be the case that there exists a production p = X → (D, C) such that C contains a connection instruction (σ, α n , γ, z, d), where z ∈ D is a wire-vertex. First, observe that from Lemma 5.2.23, we know that f : G R → G M is a saturated grammar matching with respect to the rewrite rule G R r ← − G I l − → G L . Next, we prove that no nonterminal vertex with label S in G M can satisfy the single-step context-passing relation P (and thus Q). Assume the contrary, that there exist nonterminal vertices u, u , such that u P d σ (α , α ) u and one of them has label S. If u has label S, then, the vertex u must have non-empty context which contradicts with Corollary 5.4.6. Otherwise, u has label S, which means there exists a production q which has a connection instruction to a nonterminal vertex with label S, which again contradicts Corollary 5.4.6.
We have assumed that x 0 Q d σ (α 0 , α n ) x n , therefore, there exist nonterminal vertices x 1 , . . . , x n−1 and edge labels α 1 , . . . , α n−1 , such that: x n−1 P d σ (α n−1 , α n ) x n If x 0 is outside of the image of f , then this means that all the x i are also outside of the image of f . To see this, assume the opposite. This means there exist nonterminal vertices x k , x k+1 in productions q, q such that x k is not in the image of f and x k+1 (and thus q ) are in the image of f , and moreover x k P d σ (α k , α k+1 ) x k+1 . By definition of the single-step context-passing relation, this means λ(x k ) = lhs(q ). However, x k is not in the image of f , but q is, and therefore from the Nonterminal covering condition satisfied for the saturated matching f , it means that λ(x k ) = S, which is a contradiction.
Therefore, if x 0 is outside of the image of f , then this means that each x i has label which is not used in G R , because all of these vertices are outside of the image of f and their label cannot be S (otherwise we would violate the Nonterminal covering condition). The productions which carry such labels have not been modified by the rewrite and moreover, from Lemma 5.4.5, we know that the context of each x i in G R is the same as its counterpart in G H . Therefore, we get a contradiction with the wire-consistency of G H .
Thus, it must be the case that x 0 is in the image of f . Now, we can prove that all the x i vertices are also in the image of f . Assume the opposite, therefore there exist x k , x k+1 in productions q and q , such that x k is in the image of f , but x k+1 isn't. Because x k P d σ (α k , α k+1 ) x k+1 , it follows λ(x k ) = lhs(q ) and also q has a connection instruction to x k+1 . From the Production branching condition, it follows production q is also in the image of f . But then, from the Production saturation condition, it follows that production q must have the same connection instructions as those of its pre-image. This results in a contradiction, because we know q must also have a connection instruction to x k+1 which is outside of the image of f .
Because all x i are in the image of f , then using Lemma 5.4.5, we also know that they have the same context in G M as their pre-images in G R and therefore we get a contradiction with the wire-consistency of G R .
Building on top of the results from this subsection we may now prove our first main theorem which states that a B-ESG rewrite results in a B-ESG grammar. For condition N1, consider an arbitrary edge e in G M , such that it connects two node-vertices. If e is outside of the image of f , then e is unmodified by the rewrite and therefore it must carry an encoding label, because G H also satisfies condition N1. Otherwise, e is in the image of f and again we get that e must have an encoding label, because G R satisfies condition N1.
Conditions N2 and W2 follow using the same argument. If the production p ∈ G M in question is outside of the image of f , then it is unmodified and must have the same connection instructions as its counterpart in G H which satisfies both conditions N2 and W2. Otherwise, p is in the image of f and therefore by the Production saturation condition we know that p has the same connection instructions as its pre-image in G R , which satisfies both conditions N2 and W2.
Finally, let's consider condition W1. Assume for contradiction that there exists a wire-vertex w in production p of G M , such that w has production in-degree more than one. Without loss of generality, let's assume that the production in-degree of w is two. If w is outside of the image of f , then w and its incident edges or connection instructions are unmodified by the rewrite which means that G H also contains a wire-vertex with in-degree two, which is a contradiction. Therefore, w is in the image of f . If w is not a boundary vertex, then from the no-dangling edges/connection instructions conditions, it follows that the pre-image of w under f in G R has production in-degree two, which is a contradiction. Therefore, w must be a boundary vertex, so let w = f • r(w ), where w ∈ G I .
The pre-image of w under f is then r(w ). If r(w ) has production in-degree zero in G R , this means that m • l(w ) must have production in-degree two in G H , which is a contradiction. Therefore, r(w ) has production in-degree equal to one. However, B is a B-ESG rewrite rule and therefore the inputs and outputs in corresponding productions of G L and G R are in bijection, specified by the morphisms l and r. Thus, we know that l(w ) must have production in-degree one as well. Therefore, m • l(w ) has production in-degree one. But then, in the pushout complement G K , we get that k(w ) has production in-degree zero (because G I has no edges, nor connection instructions). After computing the pushout of k and r, we see that f • r(w ) = w must have production in-degree one, which is a contradiction.
If we assume that there exists a wire-vertex with production out-degree more than one, we get a contradiction by symmetry.

Rewrites form a B-ESG pattern
We continue by showing that a B-ESG rewrite forms a B-ESG rewrite pattern together with the original grammar. Proof. Assume for contradiction that G M contains a wire-vertex w which has production in-degree zero and production out-degree zero. If w is not in the image of f , then it is unmodified by the rewrite and from the no-dangling edges/connection instructions condition, it follows that G H contains a production isolated wire-vertex, which is a contradiction. Therefore, w must be in the image of f , that is, there exists a wire-vertex w ∈ G R , such that f (w ) = w. But then, it follows that w must be a production isolated wire-vertex, which is a contradiction. We define a function F which maps production inputs from G H into production inputs of G M : where w ∈ G I is a production input g(w ) if w = s(w ) where w ∈ G K , w ∈ k(G I ) is a production input Note, that the construction is essentially the same as the one from Lemma 5.2.22. We claim that F is a bijection between the production inputs of G H and the production inputs of G M . First, the definition of F is complete in the sense that it is totally defined, because m and s are jointly surjective and also because every production input in G L is in the image of l by definition.
Next, we need to show F is well-defined, that is F (w) is a production input. In the first case, w = m • l(w ) with w ∈ G I . Then, l(w ) is also a production input and therefore r(w ) is a production input in G R by definition of B-ESG rewrite rule.
Moreover, k(w ) must also be a production input, because otherwise s • k(w ) = m • l(w ) wouldn't be one. Therefore, F (w) = f • r(w ) must also be a production input, because G M is the pushout of k and r. In the other case, w = s(w ), with w ∈ G K . Then, w is a production input. Since w is not in the image of k, it follows g(w ) is also a production input, because G M is the pushout of k and r.
F can easily be seen to be injective, because all of our morphisms in the DPO diagram are mono. Finally, we have to show that F is a surjection on the production inputs of G M . Let w be an arbitrary production input of G M . f and g are jointly surjective on G M and therefore we have to consider two cases.
In the first case, w is in the image of f . However, this also means that w is in the image of f • r, because all production inputs of G R are in the image of r. Therefore, w = f • r(w ) for some w ∈ G I . We know r(w ) is a production input and therefore l(w ) must be a production input by definition of B-ESG rewrite rule. Moreover, k(w ) must be a production input, because otherwise g • k(w ) = f • r(w ) = w wouldn't be a production input. This means m • l(w ) must be a production input, because G H is the pushout of l and k. But then, it follows by definition F (m • l(w )) = w.
In the other case, w is in the image of g and let w = g(w ) for w ∈ G K . Clearly, w is a production input, because it maps injectively into w which is also a production input. If w is in the image of k, then it follows w is also in the image of f • r = g • k.
So, we can assume w ∈ k(G I ). Then, s(w ) must be a production input as well, The main and final result of this chapter is presented next. It states that a B-ESG rewrite forms an admissible B-ESG rewrite pattern with respect to the B-ESG rewrite rule which was used. The proof follows easily by combining the results which we have established so far. Consider an arbitrary pattern instantiation: where K is the bijection between the productions and nonterminal vertices of the correspondence (G H , G M ).
Then, from Theorem 5.2.25, we know that there exists a sequence of rewrite rules s 1 , . . . , s n ∈ L(G), such that H n s 1 · · · sn H n . Using and Lemma 4.1.5, we know that H n and H n are encoded string graphs. Then, using Corollary 5.4.15, we can conclude that F s 1 · · · s n F , where s i =⇒ T * s i . Finally, we know from Theorem 5.3.16 that each s i is a string graph rewrite rule and that s i ∈ L(B), which completes the proof.
This result shows that our framework correctly represents reasoning with contextfree families of string diagrams in the sense that it respects their concrete semantics.

Discussion
In summary, a B-ESG grammar represents a family of string diagrams. A B-ESG rewrite pattern (which may be seen as a special kind of span of B-ESG grammars) represents an equational schema between two families of string diagrams. A B-ESG rewrite represents rewriting a family of string diagrams using an equational schema in a sound way. Another way of looking at this is to consider a B-ESG rewrite as an equational substitution which modifies a family of subdiagrams which appear in some larger family (cf. Example 5.4.2). The substitution is sound in the sense that the result is an equational schema whose every concrete instance can be derived using concrete instances of the rewrite rule (which is also an equational schema).
The ZX-calculus has been used as motivation for many of the constructions in this thesis, so we shall illustrate how these ideas translate into it. In the ZX-calculus, a B-ESG grammar can be used to represent a family of ZX-diagrams, which in turn may represent a quantum algorithm. The equational axioms and the derived equational rules of the ZX-calculus can be represented as B-ESG rewrite patterns. Then, a B-ESG rewrite can be used to represent a sound application of one of its equational rules to some family of ZX-diagrams. Therefore B-ESG rewrites correspond to sound transformations of families of ZX-diagrams, that is, the families are equal in the sense that they define the same linear maps. If, in addition, the initial family of ZX-diagrams models a quantum algorithm and we choose a sequence of rewrites in such a way that the resulting family may be translated back into a quantum circuit, then this would correspond to an equivalent circuit transformation. The sequence of B-ESG rewrite rules which were applied perform an equivalent circuit transformation in any context which may embed the sequence of matches that were used.

Related work
B-ESG rewrite patterns are similar to the pair grammars approach presented in [44].
In that paper the author defines a pair of graph grammars whose productions are in bijection which moreover preserves the nonterminals within them. As a result, parallel derivations are defined in a similar way to our B-ESG rewrite patterns. However, the author uses a different notion of grammar which is less expressive than ours.
The pair grammars approach has inspired the development of triple graph grammars [47]. In this approach, the author uses a triple of grammars (L, C, R), which also share a bijective correspondence between their productions. In this sense, they are similar to our B-ESG rewrite rules. However, the middle grammar C is used to relate graph elements from L to graph elements of R in a more powerful way compared to our approach. We simply use the middle grammar in order to identify the interface and interior elements for performing DPO rewrites. However, the grammar model used in [47] is based on monotonic single-pushout (SPO) productions with no notion of nonterminal elements. These grammars are not expressive enough for our purposes.
We have shown how to rewrite B-ESG grammars using B-ESG rewrite rules in a way which allows us to relate the modifications using concrete rules from the rule grammars. A similar approach is taken in [42], where the author describes how to transform High Level Replacement Systems (HLRS) using other HLRS. HLRS are a generalisation of the idea of a DPO graph grammar and thus this approach can be seen as doing grammar-on-grammar rewriting. However, the underlying transformation mechanism is based on (general) DPO rewriting and it looks unlikely that grammars which utilise such derivations can induce the languages we are interested in.
malising the simple idea of recognising specially labelled edges as fixed graphs. We also identified sufficient and necessary (up to normal form) conditions for encoded B-edNCE grammars to generate languages of string graphs. The grammars which satisfy these conditions are B-ESG grammars which are the primary objects of study in this thesis as we are only interested in languages of string graphs and not arbitrary graphs in general. We then compared their expressive power with that of !-graphs:

CF
and showed that B-ESG grammars are strictly more expressive than !-graphs with trivial overlap, which are currently the only class of !-graph languages that has been used in practice. We also showed that B-ESG grammars enjoy important decidability properties, such as the membership and match enumeration problems for string graphs, which are necessary properties for computer implementation of our framework.
After showing that B-ESG grammars can represent context-free families of string diagrams, we then demonstrated how to represent equational schemas of contextfree families of string diagrams by B-ESG rewrite rules. Finally, we described how to rewrite B-ESG grammars using B-ESG rewrite rules, such that the rewrite is sound with respect to the concrete semantics of our grammars. This corresponds to rewriting a context-free family of string diagrams using an equational schema between a pair of context-free families of string diagrams in a sound way with respect to their instantiations. Because string graphs represent morphisms in traced symmetric monoidal categories, this also means that we can do equational reasoning on contextfree families of morphisms for these categories. Moreover, all of our constructions have been kept decidable and may be implemented in software.

Future work: Implementation in software
All of the theory in this thesis has been designed with the goal of using machine support for equational reasoning. So an obvious next step is to actually implement the theory in software and in particular, implement it in Quantomatic. A computer implementation would obviously benefit from discovering efficient algorithms for the computational problems that we have described, such as the membership and match enumeration problems. While we haven't proved in what complexity class these problems are for the case of B-ESG grammars, they are NP-complete for B-edNCE grammars which implies that the complexity for the B-ESG case would be the same or worse. Therefore, we would most likely need to consider subclasses of B-ESG grammars with better complexity properties if we wish to implement more efficient algorithms for these problems. For example, graph languages consisting of connected graphs which are also of bounded degree can be parsed in polynomial time. An overview of efficient parsing algorithms for C-edNCE grammars is presented in Section 1.5 of [24] and in Section 2.7 of [18].
The software implementation would also benefit from any research into the visual representation of graph languages. For example, !-graphs have a convenient graphical representation where we draw blue boxes around the parts of the !-graph which can be copied, while ignoring the graph-theoretic details of !-vertices and their adjacent edges. This makes !-graphs simple to understand and use by domain experts who do not have any knowledge about the graph-theoretic definition of !-graphs. Designing similar visual representations for B-ESG families would also be helpful, because then the practitioners would be able to manipulate these families without requiring prior knowledge on the operation of context-free graph grammars.

Future work: First-order logic for B-ESG grammars
Another line of future work is the development of a first-order logic for B-ESG grammars. We have shown how to do equational proofs with B-ESG grammars so our framework can be seen as an equational logic. By introducing a first-order logic on top of it we will clearly increase its the usefulness. Such a logic has already been developed for !-graphs [45,32] . In the !-graph case, the logic supports quantification over the !-boxes of a !-graph, which allows us, among other things, to introduce pow-erful induction principles that can derive equational schemas from concrete rewrite rules. Figure 6.1 provides an example. 1 Figure 6.1: Induction example using !-graphs We believe it should be possible to extend the same ideas to B-ESG grammars which would then allow us to formally derive more powerful proofs which go beyond equational rewrites. The key notion of this logic is the universal quantification. In the !-graph case quantification is done over the !-boxes of a !-graph and in the B-ESG case the analogous notion of quantification is likely to be over a suitable subgrammar.

Future work: Concurrency and rule composition
We have shown how to transform B-ESG grammars using DPO rewriting. A natural next step is to see under what conditions we may parallelise this process. The first step towards this goal would be to determine the partial adhesive conditions under which the Concurrency Theorem [38] holds (it holds for any adhesive category), in a similar way to which we identified the partial adhesive conditions for DPO rewriting.
Once that is done, we will have to combine the results with the ones we have established in this thesis which guarantee the admissibility of the rewrites. The benefit of introducing parallel rewrites is obvious -the rewriting process will be faster on computers with multiple cores. Another line of future work which is similar in spirit is to describe how B-ESG rewrite rules may be composed. Instead of applying a sequence of rewrite rules one at a time, this would allow us to compose the rewrite rules into a single application.
This could be beneficial as it would make common rewrite sequence more compact.
Designing support for this is not trivial -we would either have to choose standard graph isomorphisms or redesign our theory to work with graphs with interfaces, where we keep the interfaces concrete.

Future work: Applications
B-ESG grammars are an alternative to !-graphs and they can be used to solve similar problems. So, the usual applications of verifying quantum protocols and algorithms is still viable. However, a natural question to consider is what kind of additional problems does the increased expressive power of B-ESG grammars allow us to solve.
Although the framework of B-ESG grammars is applicable to general string diagrammatic theories, many of the motivating ideas have been taken from the ZX-calculus in particular.
We have already seen that B-ESG grammars allow us to formally represent the local complementation rule of the ZX-calculus. This is an important rule which establishes a decision procedure for large classes of ZX-diagrams. Once, the B-ESG formalism has been implemented in software, then a natural next step is to also build support for the decision procedure itself.
Another useful application might be in quantum program optimisation. A quantum programming language, like Quipper [27] describes (infinite) families of quantum circuits. Our B-ESG grammars may also generate infinite families of quantum circuits (represented as ZX-diagrams), but B-ESG grammars are strictly less expressive compared to a Turing complete programming language. However, we know how to do equational reasoning with B-ESG grammars, so if we can choose a suitable orientation of our rewrite rules and appropriate tactics for controlling derivation sequences, then we can optimise our B-ESG grammars with respect to some criterion. Therefore, if we can identify fragments of a quantum programming language, like Quipper, which produce context-free families of quantum circuits, and we can describe an adequate bidirectional translation from the programming code into B-ESG grammars, then it could be possible to use our framework for program optimisation.
It might also be possible to use B-ESG rewriting to decide some properties using abstract interpretation of quantum programs. This would, of course, require identifying a suitable abstract domain.