In \cite{Craig}, we introduced a syntactically defined and highly general class of calculi known as \emph{semi-analytic}. We then demonstrated that any sufficiently strong (modal) substructural logic with a semi-analytic calculus must satisfy the Craig interpolation property. In this paper, we show that if the calculus is also terminating in a certain formal sense, then its logic has the Uniform Interpolation Property (UIP). This result has significant applications. On the positive side, it provides a uniform and modular method for proving UIP for various logics, including $\mathsf{FL_e}$, $\mathsf{FL_{ew}}$, $\mathsf{CFL_e}$, $\mathsf{CFL_{ew}}$, and their $K$, $D$, and $T$-type modal extensions, as well as $\mathsf{CPC}$, $\mathsf{K}$, and $\mathsf{KD}$. However, its more striking consequence lies in the negative direction. It extends the negative results of \cite{Craig} to logics with CIP but without UIP. In particular, it shows that the modal logics $\mathsf{K4}$ and $\mathsf{S4}$ do not have a terminating semi-analytic calculus. \textbf{keywords:} Uniform interpolation, Sequent calculi, Substructural logics, Modal logics, Subexponential modalities

Craig interpolation is a fundamental property of classical and non-classic logics with a plethora of applications from philosophical logic to computer-aided verification. The question of which interpolants can be obtained from an interpolation algorithm is of profound importance. Motivated by this question, we initiate the study of completeness properties of interpolation algorithms. An interpolation algorithm I is complete if, for every semantically possible interpolant C of an implication A → B , there is a proof P of A → B such that C is logically equivalent to I ( P ) . We establish incompleteness and different kinds of completeness results for several standard algorithms for resolution and the sequent calculus for propositional, modal, intuitionistic, and first-order logic.

Abstract A modular proof-theoretic framework was recently developed to prove Craig interpolation for normal modal logics based on generalizations of sequent calculi (e.g. nested sequents, hypersequents and labelled sequents). In this paper, we turn to uniform interpolation, which is stronger than Craig interpolation. We develop a constructive method for proving uniform interpolation via nested sequents and apply it to reprove the uniform interpolation property for normal modal logics $\textsf{K}$, $\textsf{D}$ and $\textsf{T}$. We then use the know-how developed for nested sequents to apply the same method to hypersequents and obtain the first direct proof of uniform interpolation for $\textsf{S5}$ via a cut-free sequent-like calculus. While our method is proof-theoretic, the definition of uniform interpolation for nested sequents and hypersequents also uses semantic notions, including bisimulation modulo an atomic proposition.

Abstract In this paper, a proof-theoretic method to prove uniform Lyndon interpolation (ULIP) for non-normal modal and conditional logics is introduced and applied to show that the logics, $\textsf{E}$, $\textsf{M}$, $\textsf{EN}$, $\textsf{MN}$, $\textsf{MC}$, $\textsf{K}$, and their conditional versions, $\textsf{CE}$, $\textsf{CM}$, $\textsf{CEN}$, $\textsf{CMN}$, $\textsf{CMC}$, $\textsf{CK}$, in addition to $\textsf{CKID}$ have that property. In particular, it implies that these logics have uniform interpolation (UIP). Although for some of them the latter is known, the fact that they have uniform LIP is new. Also, the proof-theoretic proofs of these facts are new, as well as the constructive way to explicitly compute the interpolants that they provide. On the negative side, it is shown that the logics $\textsf{CKCEM}$ and $\textsf{CKCEMID}$ enjoy UIP but not uniform LIP. Moreover, it is proved that the non-normal modal logics, $\textsf{EC}$ and $\textsf{ECN}$, and their conditional versions, $\textsf{CEC}$ and $\textsf{CECN}$, do not have Craig interpolation, and whence no uniform (Lyndon) interpolation.

Craig interpolation is a fundamental property of logics with a plethora of applications from philosophical logic to computer-aided verification. The question of which interpolants can be obtained from an interpolation algorithm is of profound importance. Motivated by this question, we initiate the study of completeness properties of interpolation algorithms. An interpolation algorithm ℐ is complete if, for every interpolant C of an implication A → B, there is a proof P of A → B such that C is logically equivalent to ℐ(P). We establish incompleteness and different kinds of completeness results for several standard algorithms for resolution and the sequent calculus for propositional, modal, and first-order logic.

Abstract We introduce a Gentzen-style framework, calledlayered sequent calculi, for modal logic $$\textsf{K5}$$ and its extensions $$\textsf{KD5}$$ , $$\textsf{K45}$$ , $$\textsf{KD45}$$ , $$\textsf{KB5}$$ , and $$\textsf{S5}$$ with the goal to investigate the uniform Lyndon interpolation property (ULIP), which implies both the uniform interpolation property and the Lyndon interpolation property. We obtain complexity-optimal decision procedures for all logics and present a constructive proof of the ULIP for $$\textsf{K5}$$ , which to the best of our knowledge, is the first such syntactic proof. To prove that the interpolant is correct, we use model-theoretic methods, especially bisimulation modulo literals.

In this paper, we investigate the proof complexity of a wide range of substructural systems. For any proof system P at least as strong as Full Lambek calculus, FL, and polynomially simulated by the extended Frege system for some superintuitionistic logic of infinite branching, we present an exponential lower bound on the proof lengths. More precisely, we will provide a sequence of P-provable formulas {An}n=1∞ such that the length of the shortest P-proof for An is exponential in the length of An. The lower bound also extends to the number of proof lines (proof lengths) in any Frege system (extended Frege system) for a logic between FL and any superintuitionistic logic of infinite branching. As an example, Hilbert-style proof systems for any finitely axiomatizable extension of FL that are weaker than the intuitionistic logic, in particular the usual Hilbert-style proof systems for the logics FLS for the set of structural rules S⊆{e,i,o,c}, fall in this category. We will also prove a similar result for the proof systems and logics extending Visser's basic propositional calculus BPC and its logic BPC, respectively. Finally, in the classical substructural setting, we will establish an exponential lower bound on the number of proof lines in any proof system polynomially simulated by the cut-free version of CFLew.