Abstract | ||
---|---|---|
For terminating double-pushout DPO graph rewriting systems confluence is, in general, undecidable. We show that confluence is decidable for an extension of DPO rewriting to graphs with interfaces. This variant is important due to it being closely related to rewriting of string diagrams. We show that our result extends, under mild conditions, to decidability of confluence for terminating rewriting systems of string diagrams in symmetric monoidal categories. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1007/978-3-662-54434-1_6 | ESOP |
Field | DocType | Citations |
Discrete mathematics,Graph,Computer science,Decidability,Confluence,Rewriting,Graph rewriting,Undecidable problem | Conference | 1 |
PageRank | References | Authors |
0.35 | 28 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Filippo Bonchi | 1 | 579 | 47.04 |
Fabio Gadducci | 2 | 772 | 62.94 |
Aleks Kissinger | 3 | 171 | 22.32 |
Paweł Sobociński | 4 | 609 | 45.57 |
Fabio Zanasi | 5 | 110 | 13.89 |