A generalized concurrent rule construction for double-pushout rewriting

DOI10.1007/978-3-030-78946-6_2zbMATH Open1489.68116arXiv2105.02309OpenAlexW3176303242MaRDI QIDQ2117256FDOQ2117256

Authors: Jens Kosiol, Gabriele Taentzer 

Publication date: 21 March 2022

Abstract: Double-pushout rewriting is an established categorical approach to the rule-based transformation of graphs and graph-like objects. One of its standard results is the construction of concurrent rules and the Concurrency Theorem pertaining to it: The sequential application of two rules can equivalently be replaced by the application of a concurrent rule and vice versa. We extend and generalize this result by introducing generalized concurrent rules (GCRs). Their distinguishing property is that they allow identifying and preserving elements that are deleted by their first underlying rule and created by the second one. We position this new kind of composition of rules among the existing ones and obtain a Generalized Concurrency Theorem for it. We conduct our work in the same generic framework in which the Concurrency Theorem has been presented, namely double-pushout rewriting in M-adhesive categories via rules equipped with application conditions.

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

Recommendations

• scientific article; zbMATH DE number 1497812
• Rule algebras for adhesive categories
• Double-pushout rewriting in context: rule composition and parallel independence
• Concurrency theorems for non-linear rewriting theories
• scientific article; zbMATH DE number 139800

zbMATH Keywords

graph transformationdouble-pushout rewritingconcurrency theoremmodel editing\( \mathcal{M} \)-adhesive categories

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

• Correctness of high-level transformation systems relative to nested conditions
• Title not available (Why is that?)
• Multi-amalgamation of rules with application conditions in \(\mathcal{M}\)-adhesive categories
• Fundamentals of algebraic graph transformation
• Local Confluence for Rules with Nested Application Conditions
• Title not available (Why is that?)
• Adhesive and quasiadhesive categories
• Title not available (Why is that?)
• Adhesive subcategories of functor categories with instantiation to partial triple graphs
• Rule algebras for adhesive categories
• Parallelism and concurrency of graph manipulations
• Parallelism and concurrency in high-level replacement systems
• -adhesive transformation systems with nested application conditions. Part 1: parallelism, concurrency and amalgamation
• Algebraic approach to single-pushout graph transformation
• Graph and model transformation. General framework and applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multilevel typed graph transformations
• Polymorphic sesqui-pushout graph rewriting
• Double-pushout-rewriting in \(S\)-Cartesian functor categories: rewriting theory and application to partial triple graphs
• Double-pushout rewriting in context: rule composition and parallel independence

Cited In (12)

• Multi-amalgamation of rules with application conditions in \(\mathcal{M}\)-adhesive categories
• Title not available (Why is that?)
• Concurrency theorems for non-linear rewriting theories
• Double-pushout rewriting in context: rule composition and parallel independence
• Formal Methods in Software and Systems Modeling
• Van Kampen squares for graph transformation
• Compositionality of rewriting rules with conditions
• Reversible sesqui-pushout rewriting
• Rule algebras for adhesive categories
• Polymorphic sesqui-pushout graph rewriting
• Adhesive DPO parallelism for monic matches
• A generalized concurrent rule construction for double-pushout rewriting: generalized concurrency theorem and language-preserving rule applications

This page was built for publication: A generalized concurrent rule construction for double-pushout rewriting

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