Termination of Graph Transformation Systems Using Weighted Subgraph Counting

Roy Overbeek; Jörg Endrullis

doi:10.1007/978-3-031-36709-0_5

Termination of Graph Transformation Systems Using Weighted Subgraph Counting

Roy Overbeek^*, Jörg Endrullis

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

5 Downloads (Pure)

Abstract

We introduce a termination method for the algebraic graph transformation framework PBPO $$^{+}$$, in which we weigh objects by summing a class of weighted morphisms targeting them. The method is well-defined in rm-adhesive quasitoposes (which include toposes and therefore many graph categories of interest), and is applicable to non-linear rules. The method is also defined for other frameworks, including DPO and SqPO, because we have previously shown that they are naturally encodable into PBPO $$^{+}$$ in the quasitopos setting.

Original language	English
Title of host publication	Graph Transformation
Subtitle of host publication	16th International Conference, ICGT 2023, Held as Part of STAF 2023, Leicester, UK, July 19–20, 2023, Proceedings
Editors	Maribel Fernández, Christopher M. Poskitt
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	81-101
Number of pages	21
ISBN (Electronic)	9783031367090
ISBN (Print)	9783031367083
DOIs	https://doi.org/10.1007/978-3-031-36709-0_5
Publication status	Published - 2023
Event	16th International Conference on Graph Transformation, ICGT 2023 - Leicester, United Kingdom Duration: 19 Jul 2023 → 20 Jul 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13961 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Conference on Graph Transformation, ICGT 2023
Country/Territory	United Kingdom
City	Leicester
Period	19/07/23 → 20/07/23

Bibliographical note

Funding Information:
We thank anonymous reviewers for many helpful suggestions. Both authors received funding from the Netherlands Organization for Scientific Research (NWO) under the Innovational Research Incentives Scheme Vidi (project. No. VI.Vidi.192.004).

Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Keywords

Graph transformation
Pullback-Pushout
Termination

Access to Document

10.1007/978-3-031-36709-0_5

Termination of Graph Transformation Systems Using Weighted Subgraph CountingFinal published version, 461 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Copy link address

Cite this

Overbeek, R., & Endrullis, J. (2023). Termination of Graph Transformation Systems Using Weighted Subgraph Counting. In M. Fernández, & C. M. Poskitt (Eds.), Graph Transformation: 16th International Conference, ICGT 2023, Held as Part of STAF 2023, Leicester, UK, July 19–20, 2023, Proceedings (pp. 81-101). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13961 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-36709-0_5

Overbeek, Roy ; Endrullis, Jörg. / Termination of Graph Transformation Systems Using Weighted Subgraph Counting. Graph Transformation: 16th International Conference, ICGT 2023, Held as Part of STAF 2023, Leicester, UK, July 19–20, 2023, Proceedings. editor / Maribel Fernández ; Christopher M. Poskitt. Springer Science and Business Media Deutschland GmbH, 2023. pp. 81-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7a94e16fc01b485f9b100d41d61283e8,

title = "Termination of Graph Transformation Systems Using Weighted Subgraph Counting",

abstract = "We introduce a termination method for the algebraic graph transformation framework PBPO $$^{+}$$, in which we weigh objects by summing a class of weighted morphisms targeting them. The method is well-defined in rm-adhesive quasitoposes (which include toposes and therefore many graph categories of interest), and is applicable to non-linear rules. The method is also defined for other frameworks, including DPO and SqPO, because we have previously shown that they are naturally encodable into PBPO $$^{+}$$ in the quasitopos setting.",

keywords = "Graph transformation, Pullback-Pushout, Termination",

author = "Roy Overbeek and J{\"o}rg Endrullis",

note = "Funding Information: We thank anonymous reviewers for many helpful suggestions. Both authors received funding from the Netherlands Organization for Scientific Research (NWO) under the Innovational Research Incentives Scheme Vidi (project. No. VI.Vidi.192.004). Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 16th International Conference on Graph Transformation, ICGT 2023 ; Conference date: 19-07-2023 Through 20-07-2023",

year = "2023",

doi = "10.1007/978-3-031-36709-0_5",

language = "English",

isbn = "9783031367083",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "81--101",

editor = "Maribel Fern{\'a}ndez and Poskitt, {Christopher M.}",

booktitle = "Graph Transformation",

address = "Germany",

}

Overbeek, R & Endrullis, J 2023, Termination of Graph Transformation Systems Using Weighted Subgraph Counting. in M Fernández & CM Poskitt (eds), Graph Transformation: 16th International Conference, ICGT 2023, Held as Part of STAF 2023, Leicester, UK, July 19–20, 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13961 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 81-101, 16th International Conference on Graph Transformation, ICGT 2023, Leicester, United Kingdom, 19/07/23. https://doi.org/10.1007/978-3-031-36709-0_5

Termination of Graph Transformation Systems Using Weighted Subgraph Counting. / Overbeek, Roy; Endrullis, Jörg.
Graph Transformation: 16th International Conference, ICGT 2023, Held as Part of STAF 2023, Leicester, UK, July 19–20, 2023, Proceedings. ed. / Maribel Fernández; Christopher M. Poskitt. Springer Science and Business Media Deutschland GmbH, 2023. p. 81-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13961 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Termination of Graph Transformation Systems Using Weighted Subgraph Counting

AU - Overbeek, Roy

AU - Endrullis, Jörg

N1 - Funding Information: We thank anonymous reviewers for many helpful suggestions. Both authors received funding from the Netherlands Organization for Scientific Research (NWO) under the Innovational Research Incentives Scheme Vidi (project. No. VI.Vidi.192.004). Publisher Copyright: © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2023

Y1 - 2023

N2 - We introduce a termination method for the algebraic graph transformation framework PBPO $$^{+}$$, in which we weigh objects by summing a class of weighted morphisms targeting them. The method is well-defined in rm-adhesive quasitoposes (which include toposes and therefore many graph categories of interest), and is applicable to non-linear rules. The method is also defined for other frameworks, including DPO and SqPO, because we have previously shown that they are naturally encodable into PBPO $$^{+}$$ in the quasitopos setting.

AB - We introduce a termination method for the algebraic graph transformation framework PBPO $$^{+}$$, in which we weigh objects by summing a class of weighted morphisms targeting them. The method is well-defined in rm-adhesive quasitoposes (which include toposes and therefore many graph categories of interest), and is applicable to non-linear rules. The method is also defined for other frameworks, including DPO and SqPO, because we have previously shown that they are naturally encodable into PBPO $$^{+}$$ in the quasitopos setting.

KW - Graph transformation

KW - Pullback-Pushout

KW - Termination

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

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

U2 - 10.1007/978-3-031-36709-0_5

DO - 10.1007/978-3-031-36709-0_5

M3 - Conference contribution

AN - SCOPUS:85169071798

SN - 9783031367083

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 81

EP - 101

BT - Graph Transformation

A2 - Fernández, Maribel

A2 - Poskitt, Christopher M.

PB - Springer Science and Business Media Deutschland GmbH

T2 - 16th International Conference on Graph Transformation, ICGT 2023

Y2 - 19 July 2023 through 20 July 2023

ER -

Overbeek R, Endrullis J. Termination of Graph Transformation Systems Using Weighted Subgraph Counting. In Fernández M, Poskitt CM, editors, Graph Transformation: 16th International Conference, ICGT 2023, Held as Part of STAF 2023, Leicester, UK, July 19–20, 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 81-101. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2023 Jul 12. doi: 10.1007/978-3-031-36709-0_5