Abstract
Traced monoidal closed categories are a model for higher-order functional computation. We develop a formal language of string diagrams for these categories, and a faithful interpretation in terms of certain hypergraphs. We then use the interpretation to show that string diagram rewriting can be implemented as double-pushout rewriting in a sound and complete way. Finally, we showcase our approach on the λ-calculus with explicit recursion.
| Original language | English |
|---|---|
| Title of host publication | Graph Transformation |
| Subtitle of host publication | 18th International Conference, ICGT 2025, Held as Part of STAF 2025, Koblenz, Germany, June 11–12, 2025, Proceedings |
| Editors | Jörg Endrullis, Matthias Tichy |
| Publisher | Springer |
| Pages | 24-43 |
| Number of pages | 20 |
| Edition | 1 |
| ISBN (Electronic) | 9783031947063 |
| ISBN (Print) | 9783031947056 |
| DOIs | |
| Publication status | Published - 5 Jul 2025 |
| Event | 18th International Conference on Graph Transformation, ICGT 2025, Held as Part of STAF 2025 - Koblenz, Germany Duration: 11 Jun 2025 → 12 Jun 2025 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 15720 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 18th International Conference on Graph Transformation, ICGT 2025, Held as Part of STAF 2025 |
|---|---|
| Country/Territory | Germany |
| City | Koblenz |
| Period | 11/06/25 → 12/06/25 |
Bibliographical note
Publisher Copyright:© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.
Keywords
- String diagrams
- Hypergraphs
- Rewriting
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science