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

Roy Overbeek; Jörg Endrullis; Aloïs Rosset

doi:10.1016/j.jlamp.2023.100873

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 Journal › Article › Academic › peer-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 language	English
Article number	100873
Pages (from-to)	1-25
Number of pages	25
Journal	Journal of Logical and Algebraic Methods in Programming
Volume	133
Early online date	6 Apr 2023
DOIs	https://doi.org/10.1016/j.jlamp.2023.100873
Publication status	Published - 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

Funding

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 ).

Access to Document

10.1016/j.jlamp.2023.100873

Persistent URL (handle)

Persistent link

Cite this

@article{a49bd7b293914306841eb60baa3f362b,

title = "Graph rewriting and relabeling with PBPO+: A unifying theory for quasitoposes",

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.",

author = "Roy Overbeek and J{\"o}rg Endrullis and Alo{\"i}s Rosset",

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: {\textcopyright} 2023 The Authors",

year = "2023",

month = jun,

doi = "10.1016/j.jlamp.2023.100873",

language = "English",

volume = "133",

pages = "1--25",

journal = "Journal of Logical and Algebraic Methods in Programming",

issn = "2352-2208",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Graph rewriting and relabeling with PBPO+

T2 - A unifying theory for quasitoposes

AU - Overbeek, Roy

AU - Endrullis, Jörg

AU - Rosset, Aloïs

N1 - 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

PY - 2023/6

Y1 - 2023/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85153080863&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85153080863&partnerID=8YFLogxK

U2 - 10.1016/j.jlamp.2023.100873

DO - 10.1016/j.jlamp.2023.100873

M3 - Article

AN - SCOPUS:85153080863

SN - 2352-2208

VL - 133

SP - 1

EP - 25

JO - Journal of Logical and Algebraic Methods in Programming

JF - Journal of Logical and Algebraic Methods in Programming

M1 - 100873

ER -