Patch graph rewriting

DOI10.1007/978-3-030-51372-6_8zbMATH Open1502.68157arXiv2003.06488OpenAlexW3011174127MaRDI QIDQ5100730FDOQ5100730

Authors: Roy Overbeek, Jörg Endrullis 

Publication date: 1 September 2022

Published in: Graph Transformation (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

embeddinggraph rewritingvisual language

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Cites Work

• Processes, Terms and Cycles: Steps on the Road to Infinity
• Title not available (Why is that?)
• Local termination: theory and practice
• Title not available (Why is that?)
• Double-pushout graph transformation revisited
• Title not available (Why is that?)
• Parallelism and concurrency of graph manipulations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algebraic approach to single-pushout graph transformation
• Programming Languages and Systems
• Distributed algorithms. An intuitive approach
• Title not available (Why is that?)
• The PBPO graph transformation approach
• AGREE -- algebraic graph rewriting with controlled embedding
• Graph path orderings
• Drags: a compositional algebraic framework for graph rewriting
• Double-pushout rewriting in context: rule composition and parallel independence
• Proving non-termination by finite automata
• Termination analysis for graph transformation systems

Cited In (4)

• Graph rewriting and relabeling with PBPO\textsuperscript{+}
• GrGen: A Fast SPO-Based Graph Rewriting Tool
• Graph rewriting and relabeling with PBPO\(^+\): a unifying theory for quasitoposes
• From linear term rewriting to graph rewriting with preservation of termination

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)