Reproduce “Fundamentals of Compositional Rewriting Theory” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Nicolas Behr, Russ Harmer, Jean Krivine

This research introduces Compositional Rewriting Double Categories (crDCs), a novel abstract framework using double categories and advanced fibrational structures to provide universal proofs for concurrency and associativity in rewriting systems. The framework rigorously characterizes the compositional properties of various Double Pushout (DPO) and Sesqui-Pushout (SqPO) semantics, demonstrating that generic SqPO semantics can be compositional for simple graphs, unlike generic DPO.

Key insights

  • Abstracting rewriting theories into fibrational structures within double categories enables significantly more modular, readable, and compact proofs for fundamental concurrency and associativity theorems.
  • The framework allows for determining compositionality for a given rewriting semantics purely from the properties of its direct derivations, moving beyond semantics-specific, ad-hoc derivations.
  • Generic Sesqui-Pushout (SqPO) semantics is shown to be compositional for categories like simple directed graphs (SGraph), a result not generally true for generic Double Pushout (DPO) semantics.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.