Pattern Graph Rewrite Systems
String diagrams are a powerful tool for reasoning about physical processes, logic circuits, tensor networks, and many other compositional structures. Dixon, Duncan and Kissinger introduced string graphs, which are a combinatoric representations of string diagrams, amenable to automated reasoning abo...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
2012
|
| _version_ | 1797063310704640000 |
|---|---|
| author | Kissinger, A Merry, A Soloviev, M |
| author_facet | Kissinger, A Merry, A Soloviev, M |
| author_sort | Kissinger, A |
| collection | OXFORD |
| description | String diagrams are a powerful tool for reasoning about physical processes, logic circuits, tensor networks, and many other compositional structures. Dixon, Duncan and Kissinger introduced string graphs, which are a combinatoric representations of string diagrams, amenable to automated reasoning about diagrammatic theories via graph rewrite systems. In this extended abstract, we show how the power of such rewrite systems can be greatly extended by introducing pattern graphs, which provide a means of expressing infinite families of rewrite rules where certain marked subgraphs, called !-boxes (\"bang boxes\"), on both sides of a rule can be copied any number of times or removed. After reviewing the string graph formalism, we show how string graphs can be extended to pattern graphs and how pattern graphs and pattern rewrite rules can be instantiated to concrete string graphs and rewrite rules. We then provide examples demonstrating the expressive power of pattern graphs and how they can be applied to study interacting algebraic structures that are central to categorical quantum mechanics. |
| first_indexed | 2024-03-06T20:58:00Z |
| format | Conference item |
| id | oxford-uuid:39eb831e-86e2-448e-a323-aca0b2535ecb |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:58:00Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:39eb831e-86e2-448e-a323-aca0b2535ecb2022-03-26T13:58:23ZPattern Graph Rewrite SystemsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:39eb831e-86e2-448e-a323-aca0b2535ecbDepartment of Computer Science2012Kissinger, AMerry, ASoloviev, MString diagrams are a powerful tool for reasoning about physical processes, logic circuits, tensor networks, and many other compositional structures. Dixon, Duncan and Kissinger introduced string graphs, which are a combinatoric representations of string diagrams, amenable to automated reasoning about diagrammatic theories via graph rewrite systems. In this extended abstract, we show how the power of such rewrite systems can be greatly extended by introducing pattern graphs, which provide a means of expressing infinite families of rewrite rules where certain marked subgraphs, called !-boxes (\"bang boxes\"), on both sides of a rule can be copied any number of times or removed. After reviewing the string graph formalism, we show how string graphs can be extended to pattern graphs and how pattern graphs and pattern rewrite rules can be instantiated to concrete string graphs and rewrite rules. We then provide examples demonstrating the expressive power of pattern graphs and how they can be applied to study interacting algebraic structures that are central to categorical quantum mechanics. |
| spellingShingle | Kissinger, A Merry, A Soloviev, M Pattern Graph Rewrite Systems |
| title | Pattern Graph Rewrite Systems |
| title_full | Pattern Graph Rewrite Systems |
| title_fullStr | Pattern Graph Rewrite Systems |
| title_full_unstemmed | Pattern Graph Rewrite Systems |
| title_short | Pattern Graph Rewrite Systems |
| title_sort | pattern graph rewrite systems |
| work_keys_str_mv | AT kissingera patterngraphrewritesystems AT merrya patterngraphrewritesystems AT solovievm patterngraphrewritesystems |