Compositionality of rewriting rules with conditions

DOI10.32408/COMPOSITIONALITY-3-2zbMATH Open1490.68124arXiv1904.09322OpenAlexW2938952696MaRDI QIDQ5087656FDOQ5087656

Nicolas Behr, Jean Krivine

Publication date: 1 July 2022

Published in: Compositionality (Search for Journal in Brave)

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.

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

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

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)

Cited In (15)

• Fundamentals of compositional rewriting theory
• Pregeometric spaces from Wolfram model rewriting systems as homotopy types
• Conditional rewrite rule systems with built-in arithmetic and induction
• Rewriting Theory for the Life Sciences: A Unifying Theory of CTMC Semantics
• Title not available (Why is that?)
• Concurrency theorems for non-linear rewriting theories
• Derivability of rules from rule complexes
• Title not available (Why is that?)
• Advanced model consistency restoration with higher-order short-cut rules
• Rewriting theory for the life sciences: a unifying theory of CTMC semantics
• Stochastic graph transformation for social network modeling
• A Compositional Semantics for ‘If Then’ Conditionals
• Title not available (Why is that?)
• 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)