Name
Abstract | ||
|---|---|---|
String diagrams provide an intuitive language for expressing networks of interacting processes graphically. A discrete representation of string diagrams, called string graphs, allows for mechanised equational reasoning by double-pushout rewriting. However, one often wishes to express not just single equations, but entire families of equations between diagrams of arbitrary size. To do this we define a class of context-free grammars, called B-ESG grammars, that are suitable for defining entire families of string graphs, and crucially, of string graph rewrite rules. We show that the language-membership and match-enumeration problems are decidable for these grammars, and hence that there is an algorithm for rewriting string graphs according to B-ESG rewrite patterns. We also show that it is possible to reason at the level of grammars by providing a simple method for transforming a grammar by string graph rewriting, and showing admissibility of the induced B-ESG rewrite pattern. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-21145-9_9 | GRAPH TRANSFORMATION (ICGT 2015) |
Field | DocType | Volume |
Tree-adjoining grammar,String searching algorithm,Context-sensitive grammar,Discrete mathematics,Combinatorics,Computer science,Empty string,Phrase structure grammar,Algorithm,String (computer science),Prefix grammar,String operations | Journal | 9151 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.38 |
References | Authors | |
14 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aleks Kissinger | 1 | 171 | 22.32 |
| Vladimir Zamdzhiev | 2 | 28 | 3.35 |