Categorification of Rule Algebras in Compositional Rewriting Systems

Explore a novel approach to formalizing operations in compositional rewriting systems in this 41-minute lecture by Nicolas Behr from CNRS, Université Paris Cité, IRIF. Delve into the concept of categorification of rule algebras, focusing on scenarios where the number of ways to apply a rewrite is significant. Learn about the use of double categories to capture individual rewriting steps as 2-cells, and understand the fibrational properties required for vertical source and target functors, as well as horizontal composition of cells. Discover how a presheaf calculus over 2-cells is employed to count realizations of rewriting steps or sequences. Examine the representation of rule algebra representations within this calculus and explore the categorification of rule algebras through a categorical construction involving coends. The lecture covers topics such as motivation, formalization, double categories, horizontal composition, coends, multisums, nonnegative integer coefficients, and includes examples to illustrate the concepts.

Intro
Motivation
Formalization
Double Categories
Horizontal Composition
Double Category
Coend
Multisums
Nonnegative integer coefficients
Algebra
Example
Conclusion