Compositionality of rewriting rules with conditions

DOI10.32408/COMPOSITIONALITY-3-2MaRDI QIDQ5087656zbMATHOpenAlexFDO

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

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

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

(18)

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

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)