Graph rewriting and relabeling with PBPO+: A unifying theory for quasitoposes

Roy Overbeek*, Jörg Endrullis, Aloïs Rosset

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We extend the powerful Pullback-Pushout (PBPO) approach for graph rewriting with strong matching. Our approach, called PBPO+, allows more control over the embedding of the pattern in the host graph, which is important for a large class of rewrite systems. We argue that PBPO+ can be considered a unifying theory in the general setting of quasitoposes, by demonstrating that PBPO+ can define a strict superset of the rewrite relations definable by PBPO, AGREE and DPO. Additionally, we show that PBPO+ is well suited for rewriting labeled graphs and some classes of attributed graphs, by introducing a lattice structure on the label set and requiring graph morphisms to be order-preserving.

Original languageEnglish
Article number100873
Pages (from-to)1-25
Number of pages25
JournalJournal of Logical and Algebraic Methods in Programming
Volume133
Early online date6 Apr 2023
DOIs
Publication statusPublished - Jun 2023

Bibliographical note

Funding Information:
The authors received funding from the Netherlands Organisation for Scientific Research (NWO) under the Innovational Research Incentives Scheme Vidi (project. No. VI.Vidi.192.004 ).

Publisher Copyright:
© 2023 The Authors

Fingerprint

Dive into the research topics of 'Graph rewriting and relabeling with PBPO+: A unifying theory for quasitoposes'. Together they form a unique fingerprint.

Cite this