Modular constructive Lyndon interpolation for nondistributive logics
Andrea De Domenico, Giuseppe Greco, Alessandra Palmigiano, Apostolos Tzimoulis · 2026
Read Modular constructive Lyndon interpolation for nondistributive logics by Andrea De Domenico, Giuseppe Greco, Alessandra Palmigiano, Apostolos Tzimoulis (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-17161.txt.
Introduction
De Domenico and colleagues prove the Lyndon interpolation trait for basic lattice expansion logics in any signature, using display calculi. Their proof builds the needed middle claims straight from derivations. The method is modular: new axioms need only a local check on their added rules. The work covers all signatures, not just a few. As a test case, the tense form of Holliday's core modal logic gains the same trait.
Catalog record
| CREATOR | Andrea De Domenico, Giuseppe Greco, Alessandra Palmigiano, Apostolos Tzimoulis |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89271 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.17161
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Modular constructive Lyndon interpolation for nondistributive logics Andrea De Domenico, Giuseppe Greco, Alessandra Palmigiano, Apostolos Tzimoulis Abstract We establish the Lyndon interpolation property for basic lattice expansion logics (LE-logics) in arbitrary signatures using display calculi. Our approach is constructive , yielding interpolants algorithmically from derivations, and modular , in the sense that interpolation for axiomatic extensions can be obtained by verifying a local interpolation property for the analytic structural rules corresponding to the additional axioms. To this end, we identify a class of interpolation-safe structural rules preserving local Lyndon interpolation. As applications of the general framework, we show that the tense version of Holliday’s fundamental modal logic enjoys the Lyndon interpolation property. [orcid=0000-0002-8973-7011, [email protected], ] *1 1 [orcid=0000-0002-4845-3821, [email protected], ] 1 [orcid=0000-0001-9656-7527, [email protected], ] 1 [orcid=0000-0002-6228-4198, [email protected], ] 1 keywords Craig interpolation ,Lyndon interpolation ,Non classical logics ,Lattice expansion logics ,Display calculi † † copyrightyear: 2022 † † copyright: Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). † † venue: CI-BD-SOQE 2026: Workshop on Craig Interpolation, Beth Definability, and Second-Order Quantifier Elimination, Lisbon, Portugal, 24–25 July 2026 † † address: IMDEA Software Institute, Madrid, Spain † † address: Vrije Universiteit Amsterdam, The Netherlands † † address: Department of Mathematics and Applied Mathematics, University of Johannesburg, South Africa † † address: Department of Computer Science, University of Luxembourg † † corresp: Corresponding author. † † These authors contributed equally. 1 Introduction In its classical form, the Craig interpolation property states that whenever a formula A\to B is derivable in a logic, there exists a formula C , called an interpolant , such that both A\to C and C\to B are derivable, and moreover C contains only the non-logical symbols common to A and B . More generally, in abstract formulations of interpolation, implication is replaced by the derivability relation of the logic, while the formulas A and B may be replaced by contexts or bunches of formulas, either in the language of the logic itself or in a suitable extension thereof. The interpolant C , however, remains a formula of the original language of the logic, possibly occurring within a non-empty context. The stronger Lyndon interpolation property additionally requires preservation of the polarity of propositional variables. Interpolation has deep connections with algebra, model theory, proof theory, and category theory, as well as important applications in computer science, including modular specification, formal verification, model checking, and automated reasoning. In algebraic logic, interpolation is closely related to amalgamation and superamalgamation properties, while explicitly constructing interpolants usually requires the use of analytic calculi with good structural properties. The study of interpolation in non-classical logics has produced a broad and technically diverse literature. Surveys such as D’Agostino 2008 and Fussner 2026 document the variety of semantic, algebraic, and proof-theoretic techniques developed for various modal and substructural logics. Among proof-theoretic approaches, a particularly fruitful line of research investigates interpolation via analytic calculi from which interpolants can be extracted algorithmically van der Giessen et al. 2026 ; Lyon et al. 2020 . The results of the present paper are closest to Kuznets’ modular approach to interpolation based on labelled sequent calculi Kuznets 2016 , which adapts results obtained for a class of internal sequent-like formalisms Kuznets 2015 . In this line of research, interpolants are constructed inductively from derivations in analytic labelled calculi, yielding constructive proofs of Craig and Lyndon interpolation. One of the key features of this method is its modularity: interpolation for axiomatic extensions can be established by verifying local conditions on the additional rules corresponding to frame conditions. In particular, Kuznets identified a broad class of rules for which interpolation follows uniformly: Horn-like geometric rules , which equivalently correspond to frame conditions that can be captured by quantifier-free Horn formulas. This programme has significantly expanded the scope of proof-theoretic interpolation methods for substructural modal logics. The present paper develops this modular and constructive perspective in the setting of lattice expansion logics ( LE-logics Conradie and Palmigiano 2019 ; Conradie et al. 2020 ) and their proper display calculi Greco et al. 2024 . A characteristic feature of LE-logics is that the distributive laws of conjunction and disjunction are not necessarily valid, while the settings of most existing proof-theoretic results on interpolation assume the validity of distributive laws. This nondistributive setting has recently attracted increasing attention Almeida et al. 2026 ; Holliday 2023 ; Holliday 2024 . Proper display calculi provide a particularly natural framework for this investigation, because they enjoy fundamental properties such as the subformula property and cut elimination in a modular way Greco et al. 2024 , and moreover a large class of axiomatic extensions of the basic LE-logics can be endowed with analytic calculi by algorithmically generating the analytic structural rules corresponding to the additional axioms Greco et al. 2018 ; Chen et al. 2022 . This proof-theoretic environment makes it possible to study interpolation through purely proof-theoretic criteria on structural rules, in a way analogous to the role played by frame rules in Kuznets’ approach to labelled calculi. The main contribution of the present paper is a general constructive proof of Lyndon interpolation for basic LE-logics using display calculi, together with a modular extension method for axiomatic extensions. More precisely, we show that the display calculus \mathbf{D.LE} for a basic LE-logic in any given but arbitrary signature enjoys a local Maehara interpolation property , from which effective interpolation follows. We then identify a class of structural rules, which we call interpolation-safe rules , preserving this property. These rules play a role analogous to the Horn-like geometric rules in Kuznets’ framework, but are formulated intrinsically in the setting of display calculi. As a consequence, interpolation for many axiomatic extensions of LE-logics can be established uniformly by checking local syntactic conditions on the added structural rules. Our framework applies in particular to several recently introduced lattice-based modal logics. As illustrations, we obtain constructive Lyndon interpolation results for fundamental logic and its tense modal expansions introduced in Holliday 2023 ; Holliday 2024 . These logics arise from the study of non-distributive lattice semantics motivated both by proof theory and by applications to modal reasoning and natural language semantics. Structure of the paper. In Section 2 , we recall the necessary background on LE-logics and display calculi. In Section 3 , we provide the formal definitions of the various interpolation properties and establish the local Maehara-Lyndon interpolation property for the basic calculus \mathbf{D.LE} . In Section 4 , we show how to extend the strategy to some axiomatic extensions of our base logic and showcase some examples. We conclude in Section 5 with some directions for further work. 2 Preliminaries 2.1 LE-logics and their algebraic semantics An order-type over n\in\mathbb{N} is an n -tuple \varepsilon\in\{1,\partial\}^{n} . For every order type \varepsilon , we denote its opposite order type by \varepsilon^{\partial} , that is, \varepsilon^{\partial}_{i}=1 iff \varepsilon_{i}=\partial for every 1\leq i\leq n . The language \mathcal{L}_{\mathrm{LE}}(\mathcal{F},\mathcal{G}) (from now on abbreviated as \mathcal{L}_{\mathrm{LE}} ) takes as parameters a denumerable set of proposition letters \mathsf{AtProp} , elements of which are denoted p,q,r , possibly with indexes, and disjoint sets of connectives \mathcal{F} and \mathcal{G} . Each f\in\mathcal{F} (resp. g\in\mathcal{G} ) has arity n_{f}\in\mathbb{N} (resp. n_{g}\in\mathbb{N} )