An Algebraic Approach to Formal System Metatheory
Francesco Gavazzo
Abstract
We introduce an algebraic approach to the metatheory of formal systems of term assertions akin to those of structural and natural operational semantics, type theories, rewriting systems, and equational theories. We rest on Term Relation Algebras, viz. pointfree algebras of structurally-defined predicates on terms, to give a common algebraic semantics to different kinds of formal systems, regardless of their inferential mechanisms and underlying term structures. This enables abstract reasoning about formal systems, and their metatheory, through the algebra of the term predicates they define. We give a faithfully term-free algebraization of semantically-relevant term predicates, such as parallel reduction, big-step evaluation, and applicative bisimilarity. We extend this algebraization also to fundamental metatheoretical properties of these notions - including congruence of applicative bisimilarity, determinacy of evaluation, and confluence of reduction - and prove these properties using algebraic methods.
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.
Lineage
- Weak Similarity in Higher-Order Mathematical Operational Semantics cites A Cellular Howe Theorem
- Weak Similarity in Higher-Order Mathematical Operational Semantics cites Towards a Higher-Order Mathematical Operational Semantics
- Elements of Quantitative Rewriting cites A relational theory of effects and coeffects
- Towards a Higher-Order Mathematical Operational Semantics cites A Cellular Howe Theorem
Builds on8
- A relational theory of effects and coeffectsUgo Dal Lago, Francesco GavazzoPOPL 2022 · 22 citations
- Towards a Higher-Order Mathematical Operational SemanticsSergey Goncharov, Stefan Milius, Lutz Schröder, Stelios Tsampas et al.POPL 2023 · 15 citations
- Weak Similarity in Higher-Order Mathematical Operational SemanticsHenning Urbat, Stelios Tsampas, Sergey Goncharov, Stefan Milius et al.LICS 2023 · 10 citations
- Elements of Quantitative RewritingFrancesco Gavazzo, Cecilia Di FlorioPOPL 2023 · 10 citations
- A Cellular Howe TheoremPeio Borthelle, Tom Hirschowitz, Ambroise LafontLICS 2020 · 9 citations
Related papers
- Bialgebraic Reasoning on Higher-order Program EquivalenceSergey Goncharov, Stefan Milius, Stelios Tsampas, Henning UrbatLICS 2024 · 4 citations
- Allegories of Symbolic ManipulationsFrancesco GavazzoLICS 2023
- Algebraic models of simple type theories: A polynomial approachNathanael Arkor, Marcelo FioreLICS 2020 · 10 citations
- A Type Theory for Strictly Unital ∞-CategoriesEric Finster, David Reutter, Jamie Vicary, Alex RiceLICS 2022 · 6 citations
- Substructural Abstract Syntax with Variable Binding and Single-Variable SubstitutionMarcelo Fiore, Sanjiv RanchodLICS 2025 · 3 citations
