Lune

POPL2023Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Allegories of Symbolic ManipulationsFrancesco GavazzoLICS 2023
  2. An Algebraic Approach to Formal System MetatheoryFrancesco GavazzoLICS 2026

Builds on7

  1. A graded dependent type system with a usage-aware semanticsPritam Choudhury, Harley Eades III, Richard A. Eisenberg, Stephanie WeirichPOPL 2021 · 33 citations
  2. A relational theory of effects and coeffectsUgo Dal Lago, Francesco GavazzoPOPL 2022 · 22 citations
  3. Combining Nondeterminism, Probability, and Termination: Equational and Metric ReasoningMatteo Mio, Ralph Sarkis, Valeria VignudelliLICS 2021 · 14 citations
  4. Logical Foundations of Quantitative EqualityFrancesco Dagnino, Fabio PasqualiLICS 2022 · 7 citations
  5. Effectful program distancingUgo Dal Lago, Francesco GavazzoPOPL 2022 · 7 citations

Related papers

  1. A Relational Theory of Monadic Rewriting Systems, Part IFrancesco Gavazzo, Claudia FaggianLICS 2021 · 3 citations
  2. QMaude: Quantitative Specification and Verification in Rewriting LogicRubén Rubio, Narciso Martí-Oliet, Isabel Pita, Alberto VerdejoFM 2023 · 11 citations
  3. On Generalized Metric Spaces for the Simply Typed Lambda-CalculusPaolo PistoneLICS 2021 · 8 citations
  4. Beyond Nonexpansive Operations in Quantitative Algebraic ReasoningMatteo Mio, Ralph Sarkis, Valeria VignudelliLICS 2022 · 4 citations
  5. Induction and Recursion Principles in a Higher-Order Quantitative Logic for ProbabilityGiorgio Bacci, Rasmus Ejlers MøgelbergLICS 2026
Dusk over the sea between two cliffs drawn in fine vertical lines