Patch Graph Rewriting

Roy Overbeek; Jörg Endrullis

doi:10.1007/978-3-030-51372-6_8

Patch Graph Rewriting

Roy Overbeek^*, Jörg Endrullis

^*Corresponding author for this work

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

Abstract

The basic principle of graph rewriting is the stepwise replacement of subgraphs inside a host graph. A challenge in such replacement steps is the treatment of the patch graph, consisting of those edges of the host graph that touch the subgraph, but are not part of it. We introduce patch graph rewriting, a visual graph rewriting language with precise formal semantics. The language has rich expressive power in two ways. First, rewrite rules can flexibly constrain the permitted shapes of patches touching matching subgraphs. Second, rules can freely transform patches. We highlight the framework’s distinguishing features by comparing it against existing approaches.

Original language	English
Title of host publication	Graph Transformation
Subtitle of host publication	13th International Conference, ICGT 2020, Held as Part of STAF 2020, Bergen, Norway, June 25–26, 2020, Proceedings
Editors	Fabio Gadducci, Timo Kehrer
Publisher	Springer
Pages	128-145
Number of pages	18
ISBN (Electronic)	9783030513726
ISBN (Print)	9783030513719
DOIs	https://doi.org/10.1007/978-3-030-51372-6_8
Publication status	Published - 2020
Event	13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020 - Bergen, Norway Duration: 25 Jun 2020 → 26 Jun 2020

Publication series

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

Conference

Conference	13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020
Country/Territory	Norway
City	Bergen
Period	25/06/20 → 26/06/20

Keywords

Embedding
Graph rewriting
Visual language

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/978-3-030-51372-6_8

Handle.net

Persistent link

Cite this

Overbeek, R., & Endrullis, J. (2020). Patch Graph Rewriting. In F. Gadducci, & T. Kehrer (Eds.), Graph Transformation: 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Bergen, Norway, June 25–26, 2020, Proceedings (pp. 128-145). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12150 LNCS). Springer. https://doi.org/10.1007/978-3-030-51372-6_8

Overbeek, Roy ; Endrullis, Jörg. / Patch Graph Rewriting. Graph Transformation: 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Bergen, Norway, June 25–26, 2020, Proceedings. editor / Fabio Gadducci ; Timo Kehrer. Springer, 2020. pp. 128-145 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5a45be441c224e088b47015907eb3077,

title = "Patch Graph Rewriting",

abstract = "The basic principle of graph rewriting is the stepwise replacement of subgraphs inside a host graph. A challenge in such replacement steps is the treatment of the patch graph, consisting of those edges of the host graph that touch the subgraph, but are not part of it. We introduce patch graph rewriting, a visual graph rewriting language with precise formal semantics. The language has rich expressive power in two ways. First, rewrite rules can flexibly constrain the permitted shapes of patches touching matching subgraphs. Second, rules can freely transform patches. We highlight the framework{\textquoteright}s distinguishing features by comparing it against existing approaches.",

keywords = "Embedding, Graph rewriting, Visual language",

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

year = "2020",

doi = "10.1007/978-3-030-51372-6_8",

language = "English",

isbn = "9783030513719",

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

publisher = "Springer",

pages = "128--145",

editor = "Fabio Gadducci and Timo Kehrer",

booktitle = "Graph Transformation",

note = "13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020 ; Conference date: 25-06-2020 Through 26-06-2020",

}

Overbeek, R & Endrullis, J 2020, Patch Graph Rewriting. in F Gadducci & T Kehrer (eds), Graph Transformation: 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Bergen, Norway, June 25–26, 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12150 LNCS, Springer, pp. 128-145, 13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020, Bergen, Norway, 25/06/20. https://doi.org/10.1007/978-3-030-51372-6_8

Patch Graph Rewriting. / Overbeek, Roy ; Endrullis, Jörg.

Graph Transformation: 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Bergen, Norway, June 25–26, 2020, Proceedings. ed. / Fabio Gadducci; Timo Kehrer. Springer, 2020. p. 128-145 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12150 LNCS).

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

TY - GEN

T1 - Patch Graph Rewriting

AU - Overbeek, Roy

AU - Endrullis, Jörg

PY - 2020

Y1 - 2020

N2 - The basic principle of graph rewriting is the stepwise replacement of subgraphs inside a host graph. A challenge in such replacement steps is the treatment of the patch graph, consisting of those edges of the host graph that touch the subgraph, but are not part of it. We introduce patch graph rewriting, a visual graph rewriting language with precise formal semantics. The language has rich expressive power in two ways. First, rewrite rules can flexibly constrain the permitted shapes of patches touching matching subgraphs. Second, rules can freely transform patches. We highlight the framework’s distinguishing features by comparing it against existing approaches.

AB - The basic principle of graph rewriting is the stepwise replacement of subgraphs inside a host graph. A challenge in such replacement steps is the treatment of the patch graph, consisting of those edges of the host graph that touch the subgraph, but are not part of it. We introduce patch graph rewriting, a visual graph rewriting language with precise formal semantics. The language has rich expressive power in two ways. First, rewrite rules can flexibly constrain the permitted shapes of patches touching matching subgraphs. Second, rules can freely transform patches. We highlight the framework’s distinguishing features by comparing it against existing approaches.

KW - Embedding

KW - Graph rewriting

KW - Visual language

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

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

U2 - 10.1007/978-3-030-51372-6_8

DO - 10.1007/978-3-030-51372-6_8

M3 - Conference contribution

SN - 9783030513719

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

SP - 128

EP - 145

BT - Graph Transformation

A2 - Gadducci, Fabio

A2 - Kehrer, Timo

PB - Springer

T2 - 13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020

Y2 - 25 June 2020 through 26 June 2020

ER -

Overbeek R , Endrullis J. Patch Graph Rewriting. In Gadducci F, Kehrer T, editors, Graph Transformation: 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Bergen, Norway, June 25–26, 2020, Proceedings. Springer. 2020. p. 128-145. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2020 Jun 23. doi: 10.1007/978-3-030-51372-6_8

Patch Graph Rewriting

Abstract

Publication series

Conference

Keywords

UN SDGs

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this