Compositionality of rewriting rules with conditions

DOI10.32408/COMPOSITIONALITY-3-2MaRDI QIDQ5087656zbMATH OpenOpenAlexFDO

Authors Nicolas Behr, Jean Krivine

Publication date 1 July 2022

Published in Compositionality (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Limits and colimits (products, sums, directed limits, pushouts, fiber products, equalizers, kernels, ends and coends, etc.) (18A30) Extensive, distributive, and adhesive categories (18B50) Grammars and rewriting systems (68Q42)

Abstract: We extend the notion of compositional associative rewriting as recently studied in the rule algebra framework literature to the setting of rewriting rules with conditions. Our methodology is category-theoretical in nature, where the definition of rule composition operations encodes the non-deterministic sequential concurrent application of rules in Double-Pushout (DPO) and Sesqui-Pushout (SqPO) rewriting with application conditions based upon $mathcalM$-adhesive categories. We uncover an intricate interplay between the category-theoretical concepts of conditions on rules and morphisms, the compositionality and compatibility of certain shift and transport constructions for conditions, and thirdly the property of associativity of the composition of rules.

Recommendations

• Rule algebras for adhesive categories
• A generalized concurrent rule construction for double-pushout rewriting
• Reversible sesqui-pushout rewriting
• Double-pushout rewriting in context: rule composition and parallel independence
• Concurrency theorems for non-linear rewriting theories

Cited in

(20)

• Rewriting theory for the life sciences: a unifying theory of CTMC semantics
• Concurrency theorems for non-linear rewriting theories
• Double-pushout rewriting in context: rule composition and parallel independence
• A Compositional Semantics for ‘If Then’ Conditionals
• Reversible sesqui-pushout rewriting
• Rule algebras for adhesive categories
• scientific article; zbMATH DE number 4060702 (Why is no real title available?)
• scientific article; zbMATH DE number 4090852 (Why is no real title available?)
• Derivability of rules from rule complexes
• Conditional rewrite rule systems with built-in arithmetic and induction
• Rule algebras for adhesive categories
• Rewriting theory for the life sciences: a unifying theory of CTMC semantics
• Constructions of copy rules
• Fundamentals of compositional rewriting theory
• Tracelet Hopf algebras and decomposition spaces (extended abstract)
• Advanced consistency restoration with higher-order short-cut rules
• Pregeometric spaces from Wolfram model rewriting systems as homotopy types
• Advanced model consistency restoration with higher-order short-cut rules
• Stochastic graph transformation for social network modeling
• Automated inference of graph transformation rules

This page was built for publication: Compositionality of rewriting rules with conditions

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