Elements of Quantitative Rewriting
Francesco Gavazzo, Cecilia Di Florio
Abstract
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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Logical Foundations of Quantitative Equality cites A relational theory of effects and coeffects
- A relational theory of effects and coeffects cites Effectful program distancing
- Effectful program distancing cites A relational theory of effects and coeffects
- A relational theory of effects and coeffects cites A graded dependent type system with a usage-aware semantics
- Allegories of Symbolic Manipulations cites Logical Foundations of Quantitative Equality
- Allegories of Symbolic Manipulations cites A relational theory of effects and coeffects
- An Algebraic Approach to Formal System Metatheory cites Logical Foundations of Quantitative Equality
- An Algebraic Approach to Formal System Metatheory cites A relational theory of effects and coeffects
- An Algebraic Approach to Formal System Metatheory cites Allegories of Symbolic Manipulations
Cited by top-tier papers2
Builds on7
- A graded dependent type system with a usage-aware semanticsPritam Choudhury, Harley Eades III, Richard A. Eisenberg, Stephanie WeirichPOPL 2021 · 33 citations
- A relational theory of effects and coeffectsUgo Dal Lago, Francesco GavazzoPOPL 2022 · 22 citations
- Combining Nondeterminism, Probability, and Termination: Equational and Metric ReasoningMatteo Mio, Ralph Sarkis, Valeria VignudelliLICS 2021 · 14 citations
- Logical Foundations of Quantitative EqualityFrancesco Dagnino, Fabio PasqualiLICS 2022 · 7 citations
- Effectful program distancingUgo Dal Lago, Francesco GavazzoPOPL 2022 · 7 citations
Related papers
- A Relational Theory of Monadic Rewriting Systems, Part IFrancesco Gavazzo, Claudia FaggianLICS 2021 · 3 citations
- QMaude: Quantitative Specification and Verification in Rewriting LogicRubén Rubio, Narciso Martí-Oliet, Isabel Pita, Alberto VerdejoFM 2023 · 11 citations
- On Generalized Metric Spaces for the Simply Typed Lambda-CalculusPaolo PistoneLICS 2021 · 8 citations
- Beyond Nonexpansive Operations in Quantitative Algebraic ReasoningMatteo Mio, Ralph Sarkis, Valeria VignudelliLICS 2022 · 4 citations
- Induction and Recursion Principles in a Higher-Order Quantitative Logic for ProbabilityGiorgio Bacci, Rasmus Ejlers MøgelbergLICS 2026
