Patch graph rewriting

DOI10.1007/978-3-030-51372-6_8MaRDI QIDQ5100730zbMATH OpenOpenAlexFDO

Authors Roy Overbeek, Jörg Endrullis

Publication date 1 September 2022

Published in Graph Transformation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.06488

zbMATH Keywords

embeddinggraph rewritingvisual language

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

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 the patch graph rewriting framework, a visual graph rewriting language with precise formal semantics. The language has rich expressive power in two ways. Firstly, rules can flexibly constrain the permitted shapes of patches touching matching subgraphs. Secondly, rules can freely transform patches. While the framework is designed to be easy to understand, it subsumes many approaches to graph rewriting.

Recommendations

• Pullback as a generic graph rewriting mechanism
• scientific article; zbMATH DE number 177452
• Relational graph rewritings
• Pullback rewriting and applications
• Set-theoretic graph rewriting

Cites work

• AGREE -- algebraic graph rewriting with controlled embedding
• Algebraic approach to single-pushout graph transformation
• Decreasing diagrams for confluence and commutation
• Distributed algorithms. An intuitive approach
• Double-pushout graph transformation revisited
• Double-pushout rewriting in context: rule composition and parallel independence
• Drags: a compositional algebraic framework for graph rewriting
• Graph path orderings
• scientific article; zbMATH DE number 4049095 (Why is no real title available?)
• scientific article; zbMATH DE number 4049108 (Why is no real title available?)
• scientific article; zbMATH DE number 177420 (Why is no real title available?)
• scientific article; zbMATH DE number 2016074 (Why is no real title available?)
• scientific article; zbMATH DE number 919844 (Why is no real title available?)
• scientific article; zbMATH DE number 919847 (Why is no real title available?)
• Local termination: theory and practice
• Parallelism and concurrency of graph manipulations
• Processes, Terms and Cycles: Steps on the Road to Infinity
• Programming Languages and Systems
• Proving non-termination by finite automata
• Termination analysis for graph transformation systems
• The PBPO graph transformation approach

Cited in

(5)

• Graph rewriting and relabeling with PBPO\textsuperscript{+}
• GrGen: A Fast SPO-Based Graph Rewriting Tool
• scientific article; zbMATH DE number 622432 (Why is no real title available?)
• Graph rewriting and relabeling with PBPO^+: a unifying theory for quasitoposes
• From linear term rewriting to graph rewriting with preservation of termination

Describes a project that uses

Uses Software

• AGREE
• Grez

This page was built for publication: Patch graph rewriting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5100730)