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.