On the denotation of circular and non-wellfounded proofs in linear logic with fixed points
Thomas Ehrhard, Farzad Jafarrahmani, Alexis Saurin
Abstract
This paper investigates the denotational invariants of non-wellfounded and circular proofs of linear logic with least and greatest fixed points, μLL, by providing a categorical semantics. More precisely the paper successively introduces semantics for (i) non-wellfounded pre-proofs, be they valid or not, (ii) valid pre-proofs exploiting their validity condition by considering an orthogonality construction on the given categorical model and finally (iii) circular strongly valid pre-proofs, exploiting both validity and regularity in order to define inductively the interpretation. Then the paper investigates the semantical content of the translation from finitary proofs to non-wellfounded proofs and, conversely, from (strongly valid) circular proofs to finitary proofs, showing that both translations preserve the interpretation.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext ff887244-9f67-489e-abcc-f8420f75deffBuilds on2
- Bouncing Threads for Circular and Non-Wellfounded Proofs: Towards Compositionality with Circular ProofsDavid Baelde, Amina Doumane, Denis Kuperberg, Alexis SaurinLICS 2022 · 26 citations
- Computational expressivity of (circular) proofs with fixed pointsGianluca Curzi, Anupam DasLICS 2023 · 6 citations
Related papers
- Categorical models of Linear Logic with fixed points of formulasThomas Ehrhard, Farzad JafarrahmaniLICS 2021 · 8 citations
- Logic Beyond Formulas: A Proof System on GraphsMatteo Acclavio, Ross Horne, Lutz StraßburgerLICS 2020 · 8 citations
- A proof theory of right-linear (ω-)grammars via cyclic proofsAnupam Das, Abhishek DeLICS 2024 · 1 citation
- A Characterisation Theorem for Two-Way Bisimulation-Invariant Monadic Least Fixpoint Logic Over Finite StructuresMaximilian Pflueger, Johannes Marti, Egor V. KostylevLICS 2024
- A Fixed Point Theorem on Lexicographic Lattice StructuresAngelos Charalambidis, Giannos Chatziagapis, Panos RondogiannisLICS 2020 · 1 citation
