betaFeedback

WorksComputer Science

Proof-Relevant Interpolation for Circular Proofs in Linear Logic

Abstract

First introduced for proving Craig's interpolation theorem, Maehara's method provides a constructive, proof-theoretic procedure for extracting interpolants in sequent calculus proofs. Building on this method, Saurin developed a ``proof-relevant'' interpolation theorem for first-order linear logic, in the sense that the interpolated proof is obtained by cut-introduction steps that can be reversed via cut-elimination. In this work, we extend Saurin's proof-relevant interpolation to linear logic proofs with cuts as well as to circular proofs in linear logic with fixed-points. We specifically show how Maehara's method can be extended in a proof-relevant way to work on non-cut-free and non-well-founded (but regular) proof objects, and guarantee that the interpolation procedure preserves strong validity. We also study conditions under which one can interpolate system L terms that are not necessarily in normal form.

Introduction

Logical results can often be considered at various levels, depending on whether one has a model-theoretic or proof-theoretic perspective. The basic focus of logic, the study of logical consequence, can indeed be considered from the point of view (i) of models – considering validity statement – or (ii) of provability – existence of a proof in a given deductive system – possibly (iii) of more specific provability statements – existence of cut-free or focused proofs typically – but also at the level (iv) of proofs themselves or even (v) of the proofs’ dynamics. Such perspectives are typical in type theory but also prove to be common in proof theory. In particular, when focusing on the deductive side, those distinctions partly amount to whether one consider a proof-relevant or proof-irrelevant versions of the results under consideration.

Interpolation. Craig’s Interpolation theorem [8, 9] – a central result of first-order logic which found many applications both in mathematical logic [17] and in computer science [20, 28, 16] – is typically such a result that can be considered at various levels, with semantical or deductive versions of the statement of interpolation (often connected when one has a completeness theorem) and even a cut-free provability version that is the heart of Maehara’s celebrated method. Indeed, Maehara’s method [26] happens to turn Craig’s interpolation as a direct consequence of cut-admissibility, and is thus applicable to a wide range of contexts [29, 35, 23, 19, 24, 2, 36, 17, 39] which may explain why this method is popular among proof-theorists.

From Maehara to Proof-relevant interpolation. The idea behind Maehara’s method is to consider a cut-free proof of the entailment to interpolate and to show that each sequent of the derivation can be interpolated, generating an interpolant for the conclusion sequent. Maehara’s method was recently revisited by Saurin [34] who gave a series of proof-relevant interpolation theorems based on cut-introduction, by identifying the structure of proof-relevant interpolation situation, PRIS. (See § 2.2 in the background.) Those results prove, for several logics, that if π\pi is a cut-free sequent proof of A⊢BA \vdash B, one can find an interpolant formula II in the common vocabulary of AA and BB and interpolating proofs π1,π2\pi_1,\pi_2 of A⊢IA \vdash I and I⊢BI \vdash B respectively such that π1\pi_1 composed with π2\pi_2 cut-reduces to π\pi. Saurin’s result can precisely be viewed as the proof-relevant version of Maehara’s method and it generalizes previous results by Čubrić [10, 11]. In the following we shall indistinctly speak of proof-relevant or Maehara-Čubrić interpolation for this style of interpolation results. Similarly to Saurin’s approach, Čubrić’ result is a proof-relevant version of Prawitz’ proof of the interpolation theorem that adapted Maehara’s method for natural deduction [32]. In this way, Čubrić’ result provides an interpolation result for simply typed λ\lambda-terms in normal form1^{1}.

We stress this fundamental limitation of Čubrić’ approach to λ\lambda-terms in normal forms. The assumptions of Maehara. Indeed, despite being general and flexible, Maehara’s original method strongly relies on several structural assumptions:

  1. the inductive character of sequent proofs, to reason by induction on the subderivations.

  2. cut-admissibility, to reason on cut-free proofs and benefit from the subformula property,

The restriction to cut-free proofs is unsatisfactory from both a logical and a computational point of view, indeed (i) the logic under study may not satisfy a full cut-elimination theorem (e.g. cut-admissibility up to analytic cuts), cut-elimination induces a size blow-up of proofs, resulting in much larger interpolants. (ii) from the computational perspective of Čubrić and Saurin’s works, this restriction is a severe limitation: for instance, Čubrić result applies to normal forms only and therefore requires to first normalise λ\lambda-terms before interpolating. Why interpolating circular proofs with cuts. In the present paper we are interested in strengthening interpolation results for fixed-point logics by proving their proof-relevant counterpart. In order to do that, we will show how one can weaken the two assumptions mentioned in the previous paragraph in order to do proof-relevant interpolation in presence of cuts as well as for circular proofs. Additionally, proof-relevant interpolation over circular proofs must also preserve the validity condition specified by the proof system, which ensures the soundness of circular proofs. This is not automatic, and addressing it is one of the main technical points of this paper. The focus on circular proofs adds a further motivation for interpolating proofs with cuts. Indeed, while μLL∞\mu\mathrm{LL}^{\infty} has a cut-elimination theorem, regularity of a proof is not preserved by cut-elimination in general2^{2}.

Related works. To the best of our knowledge, we present the first results on (i) proof-relevant interpolation (ii) for circular proofs (iii) with cuts altogether. On the other hand, each of these three topics has been investigated independently in various prior works:

(i) Proof-relevant interpolation: the most closely related work in this direction is of course Saurin’s proof-relevant interpolation theorems for a variety of sequent calculi (and term-calculi for sequent calculus) [34] that we extend here. In the early 90s, Čubrić exploited Prawitz’ interpolation theorem in natural deduction [32] to prove an interpolation result for the simply typed λ\lambda-calculus as well as a corresponding factorisation result for bicartesian closed categories [10, 11] later extended by Matthes [27] to a natural deduction with general elimination rules. Recently, Veltri and Wan proved a proof-relevant interpolation theorem for the non-associative Lambek-calculus, formalized in Agda [41]. (ii) Interpolation for fixed-point logics and circular proofs: After the seminar results by Agostino et al [14, 15] on interpolation for the modal μ\mu-calculus, several works contributed to interpolation for the modal μ\mu-calculus using circular, or cyclic, proof systems both for Craig and Lyndon’s interpolation [2, 22] and Uniform interpolation [3]. The techniques extending Maehara’s method to circular proofs are due to Shamkanov in the setting of Gödel-Löb provability logic [36]. Compared to our work, the absence of proof-relevance allow quite drastic modifications on proofs, for instance regularisation.

(iii) Interpolation for proofs with cuts: While several works aimed at extending interpolation theorems to incorporate some form of cuts [6, 21, 23, 31, 40, 25, 7], typically to prove interpolation in presence of analytic cuts and semi-analytic rules [38], most did not directly investigate how the cut inference itself impacts directly the interpolation process itself (that is the synthesis of the interpolant formula). Among the works on interpolation theorems in the presence of cuts, we should refer to Hetzl and Jalali’s work on completeness of interpolation algorithms [21], van der Giessen’s lecture notes on interpolation which prove interpolation in the presence of analytic cuts [40], a short abstract by Lolic that reports some results interpolation with cuts [25] and of course Fitting’s book that investigate interpolation for modal and intuitionistic logic and cuts [18].

Contributions and organisation of the paper. Section 2 provides some background on μ\muLL circular proofs and on proof-relevant interpolation. Then, we extend LL proof-relevant interpolation to proofs with cuts in Section 3 thus providing the first proof-relevant treatment of proofs with cuts and generalising several Craig’s interpolation methods with cuts; we also transfer this result to a computational system L generalising Saurin’s result on normal system L terms. Last, we consider in Section 4 the problem of proof-relevant interpolation for circular proofs with cuts in propositional μ\muLL∞^\infty. We restrict to a better behaved (but less general) class of circular proofs called strongly valid, which we show to be closed under our interpolation procedure. This result provides a first step towards an interpolation theorem for all valid proofs in first order μ\muLL∞^\infty. We conclude in Section 5.

Background

Circular proofs for linear logic with least and greatest fixed-points

For simplifying the background presentation, we first introduce a common framework, μ\muLLP∞^\infty_{\mathrm{P}}, in which our background notions are set. The following sections will focus on two fragments of this logic: the fixed-point-free fragment, LL, and the FO quantifier free, μ\muLLP∞^\infty_{\mathrm{P}} respectively.

We assume a first-order language L\mathcal{L} without equality nor function symbols for simplicity. The language of first-order linear logic formulas with least and greatest fixed-points (or μ\muLL formulas) and its deduction system, are defined in the following way:

Definition 1 (μ\muLL formulas). We assume to be given countable sets of (i) atomic formulas equipped with an involution inducing a partitioning between positive atoms, written a(x⃗)a(\vec{x}) (or just aa), and negative atoms, written a⊥(x⃗)a^\bot(\vec{x}) (or just a⊥a^\bot) and of (ii) fixed-point variables, written X,Y,Z,…X,Y,Z,\ldots such that X⊥=XX^\bot=X. μ\muLL formulas are defined inductively as:

F::=a⊥(x⃗)∣⊥∣⊤∣F&F∣F&F∣?F∣∀xF∣a(x⃗)∣1∣0∣F⊗F∣F⊕F∣!F∣∃xF∣X∣μX.F∣νX.F(1)\begin{aligned} F &::= a^\bot(\vec{x}) \mid\bot\mid\top\mid F \mathbin{\&} F \mid F \mathbin{\&} F \mid?F \mid\forall xF \\ &\quad\mid a(\vec{x}) \mid1 \mid0 \mid F \mathbin{\otimes} F \mid F \mathbin{\oplus} F \mid!F \mid\exists xF \\ &\quad\mid X \mid\mu X.F \mid\nu X.F \tag*{(1)} \end{aligned}

A LL formula is a formula build using only the first two lines of the above grammar. Linear negation is defined as extending the LL involution on LL formulas (changing a⊥a^{\perp}, ⊥\bot, ⊤\top, &\mathbin{\&}, ⊥\mathbin{\bot}, ?? into aa, 11, 00, ⊗\otimes, ⊕\oplus, ∃\exists, !! respectively) to fixed-points constructs: (μX.F)⊥=νX.F⊥(\mu X.F)^{\perp} = \nu X.F^{\perp} (note that μ\mu, ν\nu bind fixed-point variables). A one-sided µLL sequent is an ordered list of µLL formulas usually written ⊢Γ\vdash\Gamma.

Definition 2 (µLL∞ and LL sequent calculus). The inference rules of µLL∞ (resp. LL) sequent calculus are given by the rows a, b and d in Figure 1 (resp. rows a, b and c in Figure 1). The colored formulas in each inference rule define the ancestor (or subocurrence) relation between the conclusion and the premises of the rules.

Figure 1. µLL∞ inferences: (a) Propositional MALL inferences (no rule for 0); (b) LL exponential inferences; (c) First-order inferences (in (∀), x∉FV⁡(Γ)x \notin\operatorname{FV}(\Gamma)); (d) Fixed-point inferences.

Remark 3. For µLL∞ proofs, we restrict ourselves to the propositional fragment µLL∞, since the cut-elimination procedure for circular proofs in [33], that is used in the Theorem 37, considers only propositional formulas. For a complete treatment of quantifiers, one should use parametrized fixed-point variables and respective unfolding rules, as in [1]. We leave this for future work.

We represent the tree structure of µLL∞ derivations using derivation graphs, after [5].

Definition 4 (µLL∞ derivation graph). A µLL∞ derivation graph is a tuple D=(V,s,r,p)\mathcal{D}=(V,s,r,p) where VV is a set of vertices, s:V→Seqss:V\to\mathit{Seqs} is a total function labelling vertices with sequents in µLL, r:V→Rulesr:V\to\mathit{Rules} is a partial function labelling vertices with inference rules in µLL∞, p:N×V→Vp:\mathbb{N}\times V\to V is a partial function that maps a number nn and a vertex vv, with a vertex v′v', such that v′v' is labeled by the nthn^{\mathrm{th}} premise of the rule r(v)r(v) over the sequent s(v)s(v), and for every v∈Vv\in V, ⊢s(p1(v)) … ⊢s(pm(v))⊢s(v)(r(v))\frac{\vdash s(p_1(v))\ \ldots\ \vdash s(p_m(v))}{\vdash s(v)}(r(v)) is an instance of the rule r(v)r(v) in µLL∞, with mm premises. A vertex B∈VB\in V such that r(B)r(B) is undefined is called a bud node. The set of bud nodes of D\mathcal{D}, is written as Bud⁡(D)\operatorname{Bud}(\mathcal{D}). If VV is finite, we say that D\mathcal{D} is a finite derivation graph.

A µLL∞ derivation graph D\mathcal{D} can be seen as a directed graph (V,E)(V,E) where the set of edges is defined as E={(v,pj(v))∣v∈V and pj(v) is defined}E=\{(v,p_j(v))\mid v\in V\text{ and }p_j(v)\text{ is defined}\}. Moreover, D\mathcal{D} is said to be a derivation tree, if its directed graph is a tree. We name the root of the tree as root⁡(D)∈V\operatorname{root}(\mathcal{D})\in V and s(root⁡(D))s(\operatorname{root}(\mathcal{D})) the conclusion of the tree. Note that the ancestor relation can be extended by transitivity to formulas of non-consecutive sequents of a derivation graph.

Definition 5 (LL proof). An LL open proof π\pi of a sequent ⊢Γ\vdash\Gamma (written as π⊢Γ\pi\vdash\Gamma) is a finite derivation tree with conclusion ⊢Γ\vdash\Gamma such that all its formulas (resp. inferences) are LL formulas (resp. inferences). An LL proof π\pi is an open proof such that Bud⁡(π)=∅\operatorname{Bud}(\pi)=\varnothing.

Due to the recursive nature of the fixed-point rules, it is possible to construct infinite derivation trees even in the absence of cuts and contractions. Such infinite derivation trees are referred to as μLLP∞\mu\mathrm{LL}^{\infty}_{P} pre-proofs. In some cases, these infinite trees contain only finitely many distinct subtrees. When this occurs, we call the derivation trees regular. Such regular infinite trees can be finitely represented as trees with back-edges that form cycles, yielding what are known as μLLPω\mu\mathrm{LL}^{\omega}_{P} pre-proofs.

Definition 6 (μLLω\mu\mathrm{LL}^{\omega} pre-proof graph). A μLLω\mu\mathrm{LL}^{\omega} pre-proof graph (or simply pre-proof) of the sequent ⊢Γ\vdash\Gamma, is a tuple P=(D,R)\mathcal{P}=(\mathcal{D},\mathcal{R}), where D=(V,s,r,p)\mathcal{D}=(V,s,r,p) is a μLL∞\mu\mathrm{LL}^{\infty} finite derivation tree and R:Bud⁡(D)→V\mathcal{R}:\operatorname{Bud}(\mathcal{D})\to V is a total function, that maps each one of the bud nodes B∈Bud⁡(D)B\in\operatorname{Bud}(\mathcal{D}) to an internal node on the path from root⁡(D)\operatorname{root}(\mathcal{D}) to BB, called a companion, satisfying that if R(B)=C\mathcal{R}(B)=C, then r(C)r(C) is defined and s(B)=s(C)s(B)=s(C). We say that P\mathcal{P} is an open pre-proof if R\mathcal{R} is not defined for all B∈Bud⁡(D)B\in\operatorname{Bud}(\mathcal{D}).

The graph of a pre-proof P=(D,R)\mathcal{P}=(\mathcal{D},\mathcal{R}), written as GP\mathcal{G}_{\mathcal{P}}, is the graph obtained after adding the edges induced by R\mathcal{R} and deleting the bud vertices. Specifically, GP=(V′,s,r,p′)\mathcal{G}_{\mathcal{P}}=(V',s,r,p') where, V′=V∖Bud⁡(D)V'=V\setminus\operatorname{Bud}(\mathcal{D}) and p′p' is defined for any jj as: pj′(v)=R(pj(v))p'_j(v)=\mathcal{R}(p_j(v)) if pj(v)∈Bud⁡(D)p_j(v)\in\operatorname{Bud}(\mathcal{D}), or pj′(v)=pj(v)p'_j(v)=p_j(v) otherwise. Soundness of μLLω\mu\mathrm{LL}^{\omega} pre-proofs is ensured by imposing a correctness criterion known as the progress or validity or global trace condition:

Definition 7 (Traces and validity). Let P\mathcal{P} be a μLLω\mu\mathrm{LL}^{\omega} pre-proof. A trace over a (possibly infinite) path (vi)i∈ω(v_i)_{i\in\omega} in the graph GP\mathcal{G}_{\mathcal{P}}, is defined as a sequence of formulas (Fi)i∈ω(F_i)_{i\in\omega}, such that for each index ii, we have Fi∈s(vi)F_i\in s(v_i) and either Fi→Fi+1F_i\to F_{i+1} or Fi=Fi+1F_i=F_{i+1}, where the relation →\to denotes the Fischer-Ladner subformula relation, defined as follows:

References

  1. [1]Bahareh Afshari, Sebastian Enqvist, and Graham E Leigh. Cyclic proofs for the first-order μ-calculus. Logic Journal of the IGPL, 32(1):1–34, 02 2024. arXiv:https://academic.oup.com/jigpal/article-pdf/32/1/1/56586573/jzac053.pdf, doi:10.1093/jigpal/jzac053.
  2. [2]Bahareh Afshari and Graham E. Leigh. Lyndon interpolation for modal μ-calculus. In Aybüke Özgün and Yulia Zinova, editors, Language, Logic, and Computation - 13th International Tbilisi Symposium, TbiLLC 2019, Batumi, Georgia, September 16-20, 2019, Revised Selected Papers, volume 13206 of Lecture Notes in Computer Science, pages 197–213. Springer, 2019. doi:10.1007/978-3-030-98479-3\_10.
  3. [3]Bahareh Afshari, Graham E. Leigh, and Guillermo Menéndez Turata. Uniform interpolation from cyclic proofs: The case of modal mu-calculus. In Anupam Das and Sara Negri, editors, Automated Reasoning with Analytic Tableaux and Related Methods - 30th International Conference, TABLEAUX 2021, Birmingham, UK, September 6-9, 2021, Proceedings, volume 12842 of Lecture Notes in Computer Science, pages 335–353. Springer, 2021. doi:10.1007/978-3-030-86059-2\_20.DOI
  4. [4]David Baelde, Amina Doumane, and Alexis Saurin. Infinitary Proof Theory: the Multiplicative Additive Case. In Jean-Marc Talbot and Laurent Regnier, editors, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016), volume 62 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1–42:17, Dagstuhl, Germany, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.42, doi:10.4230/LIPIcs.CSL.2016.42.DOI
  5. [5]James Brotherston. Sequent calculus proof systems for inductive definitions. 2006.
  6. [6]Alessandra Carbone. Interpolants, cut elimination and flow graphs for the propositional calculus. Ann. Pure Appl. Log., 83(3):249–299, 1997. doi:10.1016/S0168-0072(96)00019-X.DOI
  7. [7]Simon Corbard and Anela Lolic. Efficient interpolation beyond cut-free proofs: Admissible cuts and optimized extraction. In Zhiming Liu, Adnan Saoud, and Heike Wehrheim, editors, Theoretical Aspects of Computing - ICTAC 2025 - 22nd International Colloquium, Marrakech, Morocco, November 24-28, 2025, Proceedings, volume 16237 of Lecture Notes in Computer Science, pages 185–201. Springer, 2025. doi:10.1007/978-3-032-11176-0\_12.DOI
  8. [8]William Craig. Linear reasoning. A new form of the Herbrand-Gentzen theorem. J. Symb. Log., 22(3):250–268, 1957. doi:10.2307/2963593.DOI
  9. [9]William Craig. Three uses of the herbrand-gentzen theorem in relating model theory and proof theory. J. Symb. Log., 22(3):269–285, 1957. doi:10.2307/2963594.DOI
  10. [10]Djordje Cubric. Results in categorical proof theory. PhD thesis, McGill University, 1993.
  11. [11]Djordje Cubric. Interpolation property for bicartesian closed categories. Arch. Math. Log., 33(4):291–319, 1994. doi:10.1007/BF01270628.DOI
  12. [12]Pierre-Louis Curien and Hugo Herbelin. The duality of computation. In Martin Oderksy and Philip Wadler, editors, Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming (ICFP ’00), Montreal, Canada, September 18-21, 2000, pages 233–243. ACM, 2000. doi:10.1145/351240.351262.DOI
  13. [13]Pierre-Louis Curien and Guillaume Munch-Maccagnoni. The duality of computation under focus. In IFIP TCS, volume 323, pages 165–181. Springer, 2010.arxiv.org/abs/1006.2283
  14. [14]Giovanna D’Agostino and Marco Hollenberg. Logical questions concerning the mu-calculus: Interpolation, lyndon and los-tarski. J. Symb. Log., 65(1):310–332, 2000. doi:10.2307/2586539.
  15. [15]Giovanna D’Agostino and Giacomo Lenzi. On modal mu-calculus with explicit interpolants. J. Appl. Log., 4(3):256–278, 2006. URL: https://doi.org/10.1016/j.jal.2005.06.008, doi:10.1016/J.JAL.2005.06.008.
  16. [16]Gerard R. Renardel de Lavalette. Interpolation in computing science: the semantics of modularization. Synth., 164(3):437–450, 2008. URL: https://doi.org/10.1007/s11229-008-9358-y, doi:10.1007/S11229-008-9358-Y.
  17. [17]Solomon Feferman. Harmonious logic: Craig’s interpolation theorem and its descendants. Synthèse, 164(3):341–357, 2008. URL: https://doi.org/10.1007/s11229-008-9354-2, doi:10.1007/S11229-008-9354-2.
  18. [18]Melvin Fitting. Proof Methods for Modal and Intuitionistic Logics, volume 169. Synthese Library, 1983.DOI
  19. [19]Melvin Fitting. Linear reasoning in modal logic. J. Symb. Log., 49(4):1363–1378, 1984. doi:10.2307/2274285.DOI
  20. [20]Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar, and Kenneth L. McMillan. Abstractions from proofs. SIGPLAN Not., 39(1):232–244, jan 2004. doi:10.1145/982962.964021.DOI
  21. [21]Stefan Hetzl and Rahleeh Jalali. On the completeness of interpolation algorithms. In Pawel Sobocinski, Ugo Dal Lago, and Javier Esparza, editors, Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024, Tallinn, Estonia, July 8-11, 2024, pages 45:1–45:13. ACM, 2024. doi:10.1145/3661814.3662112.DOI
  22. [22]Johannes Kloibhofer and Yde Venema. Interpolation for the two-way modal μ-calculus. In 40th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2025, Singapore, June 23-26, 2025, pages 155–168. IEEE, 2025. doi:10.1109/LICS65433.2025.00019.DOI
  23. [23]TOMASZ KOWALSKI and HIROAKIRA ONO. Analytic cut and interpolation for bi-intuitionistic logic. The Review of Symbolic Logic, 10(2):259–283, 2017. doi:10.1017/S175502031600040X.DOI
  24. [24]Roman Kuznets. Multicomponent proof-theoretic method for proving interpolation properties. Ann. Pure Appl. Log., 169(12):1369–1418, 2018. URL: https://doi.org/10.1016/j.apal.2018.08.007, doi:10.1016/J.APAL.2018.08.007.
  25. [25]Anela Lolic. Interpolation Properties of Proofs with Cuts. Informal proceedings of the 13th International Conference Logic and Applications LAP 2024: Book of Abstracts, p. 31–33, 2024.
  26. [26]Shoji Maehara. On the interpolation theorem of Craig. Sūgaku, 12:235–237, 1960.
  27. [27]Ralph Matthes. Interpolation for natural deduction with generalized eliminations. In Reinhard Kahl, Peter Schroeder-Heister, and Robert Stärk, editors, Proof Theory in Computer Science, pages 153–169, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg.
  28. [28]Kenneth L. McMillan. Interpolation and model checking. In Handbook of Model Checking., pages 421–446. 2018. doi:10.1007/978-3-319-10575-8\_14.DOI
  29. [29]Grigori Mints. Interpolation theorems for intuitionistic predicate logic. Ann. Pure Appl. Log., 113(1-3):225–242, 2001. doi:10.1016/S0168-0072(01)00060-4.
  30. [30]Guillaume Munch-Maccagnoni. Syntax and Models of a non-Associative Composition of Programs and Proofs. PhD thesis, Univ. Paris Diderot, 2013.
  31. [31]Hiroakira Ono and Katsuhiko Sano. Analytic cut and mints - symmetric interpolation method for bi-intuitionistic tense logic. In David Fernández-Duque, Alessandra Palmigiano, and Sophie Pinchinat, editors, Advances in Modal Logic, AiML 2022, Rennes, France, August 22-25, 2022, pages 601–623. College Publications, 2022. URL: http://www.aiml.net/volumes/volume14/34-Ono-Sano.pdf.
  32. [32]Dag Prawitz. Natural Deduction: A Proof-Theoretical Study. Dover Publications, Mineola, N.Y., 1965.
  33. [33]Alexis Saurin. A linear perspective on cut-elimination for non-wellfounded sequent calculi with least and greatest fixed-points. In Revantha Ramanayake and Josef Urban, editors, Automated Reasoning with Analytic Tableaux and Related Methods, pages 203–222, Cham, 2023. Springer Nature Switzerland.DOI
  34. [34]Alexis Saurin. Interpolation as Cut-Introduction: On the Computational Content of Craig-Lyndon Interpolation. In Maribel Fernández, editor, 10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025), volume 337 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:21, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2025.32, doi:10.4230/LIPIcs.FSCD.2025.32.DOI
  35. [35]Kurt Schütte. Proof theory, volume 85. Springer, 1977.DOI
  36. [36]D. S. Shamkanov. Circular proofs for the Gödel-Löb provability logic. Mathematical Notes, 96(3), 2014. URL: https://doi.org/10.1134/S0001434614090326.
  37. [37]Christoph Sprenger and Mads Dam. On the structure of inductive reasoning: Circular and tree-shaped proofs in the μcalculus. In Andrew D. Gordon, editor, Foundations of Software Science and Computation Structures, pages 425–440, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.
  38. [38]Amirhossein Akbar Tabatabai and Raheleh Jalali. Universal proof theory: Semi-analytic rules and craig interpolation. Ann. Pure Appl. Log., 176(1):103509, 2025. URL: https://doi.org/10.1016/j.apal.2024.103509, doi:10.1016/J.APAL.2024.103509.
  39. [39]Jouko A. Väänänen. The craig interpolation theorem in abstract model theory. Synth., 164(3):401–420, 2008. URL: https://doi.org/10.1007/s11229-008-9357-z, doi:10.1007/S11229-008-9357-z.
  40. [40]Iris van der Giessen. Interpolation through the Lens of Proof Theory. Lecture notes for Logic Summer School at ANU 2024 Canberra, Australia, 2024. URL: https://comp.anu.edu.au/lss/lectures/2024/Australia_course_notes.pdf.
  41. [41]Niccolò Veltri and Cheng-Syuan Wan. An agda formalization of nonassociative lambek calculus and its metatheory. In Gian Luca Pozzato and Tarmo Uustalu, editors, Automated Reasoning with Analytic Tableaux and Related Methods - 34th International Conference, TABLEAUX 2025, Reykjavik, Iceland, September 27-29, 2025, Proceedings, volume 15980 of Lecture Notes in Computer Science, pages 433–452. Springer, 2025. doi:10.1007/978-3-032-06085-3\_23.DOI

Paper details

vlnc:W_twkdv2gc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents