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

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)

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