We introduce a general theory of quantitative and metric rewriting systems, namely systems with a rewriting
relation enriched over quantales modelling abstract quantities. We develop theories of abstract and term-based
systems, refining cornerstone results of rewriting theory (such as Newman’s Lemma, Church-Rosser Theorem,
and critical pair-like lemmas) to a metric and quantitative setting. To avoid distance trivialisation and lack of
confluence issues, we introduce non-expansive, linear term rewriting systems, and then generalise the latter
to the novel class of graded term rewriting systems. These systems make quantitative rewriting modal and
context-sensitive, this way endowing rewriting with coeffectful behaviours.
Thu 19 JanDisplayed time zone: Eastern Time (US & Canada) change
Thu 19 Jan
Displayed time zone: Eastern Time (US & Canada) change
10:20 - 12:00 | |||
10:20 25mTalk | A Type-Based Approach to Divide-and-Conquer Recursion in Coq POPL Pedro da Costa Abreu Junior Purdue University, Benjamin Delaware Purdue University, Alex Hubers University of Iowa, Christa Jenkins University of Iowa, J. Garrett Morris University of Iowa, Aaron Stump University of Iowa DOI | ||
10:45 25mTalk | Elements of Quantitative RewritingVirtual POPL DOI | ||
11:10 25mTalk | The Geometry of Causality: Multi-token Geometry of Interaction and Its Causal Unfolding POPL Simon Castellan University of Rennes; Inria; CNRS; IRISA, Pierre Clairambault Université Aix-Marseille; Université de Toulon; CNRS; LIS DOI | ||
11:35 25mTalk | Deconstructing the Calculus of Relations with Tape Diagrams POPL Filippo Bonchi University of Pisa, Alessandro Di Giorgio University of Pisa, Alessio Santamaria University of Pisa; University of Sussex DOI |