Confluence of Graph Rewriting with Interfaces

被引：13

作者：

Bonchi, Filippo ^{[1
]}

Gadducci, Fabio ^{[2
]}

Kissinger, Aleks ^{[3
]}

Sobocinski, Pawel ^{[4
]}

Zanasi, Fabio ^{[5
]}

机构：

[1] CNRS, ENS Lyon, Lyon, France

[2] Univ Pisa, Pisa, Italy

[3] Radboud Univ Nijmegen, Nijmegen, Netherlands

[4] Univ Southampton, Southampton, Hants, England

[5] UCL, London, England

来源：

PROGRAMMING LANGUAGES AND SYSTEMS (ESOP 2017): 26TH EUROPEAN SYMPOSIUM ON PROGRAMMING | 2017年 / 10201卷

关键词：

Confluence; DPO rewriting systems; Adhesive categories; PROPs; String diagrams; CATEGORIES; ALGEBRA; SYSTEMS;

D O I：

10.1007/978-3-662-54434-1_6

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：141 / 169

页数：29

共 48 条

[1] [Anonymous], 1993, TERM GRAPH REWRITING
[2] Baez JC, 2015, THEOR APPL CATEG, V30, P836
[3] Baldan P, 2011, LECT NOTES COMPUT SC, V6907, P48, DOI 10.1007/978-3-642-22993-0_8
[4] FINITE COMPLETE REWRITING-SYSTEMS AND THE COMPLEXITY OF THE WORD PROBLEM
BAUER, G
OTTO, F
[J]. ACTA INFORMATICA, 1984, 21 (05) : 521 - 540
[5] Bonchi Filippo, 2014, CONCUR 2014 - Concurrency Theory. 25th International Conference, CONCUR 2014. Proceedings: LNCS 8704, P435, DOI 10.1007/978-3-662-44584-6_30
[6] Rewriting modulo symmetric monoidal structure
Bonchi, Filippo
Gadducci, Fabio
Kissinger, Aleks
Sobocinski, Pawel
Zanasi, Fabio
[J]. PROCEEDINGS OF THE 31ST ANNUAL ACM-IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2016), 2016, : 710 - 719
[7] Bonchi F, 2015, ACM SIGPLAN NOTICES, V50, P515, DOI [10.1145/2775051.2676993, 10.1145/2676726.2676993]
[8] Synthesising CCS bisimulation using graph rewriting
Bonchi, Filippo
Gadducci, Fabio
Koenig, Barbara
[J]. INFORMATION AND COMPUTATION, 2009, 207 (01) : 14 - 40
[9] Conditional Reactive Systems
Bruggink, H. J. Sander
Cauderlier, Raphael
Huelsbusch, Mathias
Koenig, Barbara
[J]. IARCS ANNUAL CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE (FSTTCS 2011), 2011, 13 : 191 - 203
[10] Normal forms for algebras of connections
Bruni, R
Gadducci, F
Montanari, U
[J]. THEORETICAL COMPUTER SCIENCE, 2002, 286 (02) : 247 - 292

← 1 2 3 4 5 →