betaFeedback

WorksComputer Science

The Density of Interpolants in Modal Logic: First Results

Abstract

We initiate a quantitative study of interpolation in propositional modal logic. Instead of asking only whether a logic has Craig or uniform interpolation, we measure the density of formulas, or pairs of formulas, admitting interpolants. For quasi-normal modal logics, formulas of bounded modal depth over finite signatures are counted modulo logical equivalence. We show that interpolation failure is local to cells determined by the retained signature, yielding product decompositions of both uniform and Craig interpolation densities. These decompositions allow us to analyse their asymptotic behaviour as either the retained or the forgotten signature grows. When the retained signature grows, we obtain general results for all quasi-normal modal logics; when the forgotten signature grows, the behaviour is subtler, particularly when formulas are counted after existential quantification over forgotten variables. For locally tabular logics, we introduce cell incompatibility graphs and use them for a fine-grained analysis covering tabular logics, the difference logic Diff, and bounded-depth extensions of Grz.

Introduction

The Craig interpolation property states that whenever an implication φ→ψ\varphi\to\psi is valid, there exists a formula θ\theta, using only the propositional variables common to φ\varphi and ψ\psi, such that both φ→θ\varphi\to\theta and θ→ψ\theta\to\psi are valid [5]. Uniform interpolation strengthens this requirement: given a formula φ\varphi and a retained signature σ\sigma, one seeks a single formula over σ\sigma that captures all consequences of φ\varphi expressible in σ\sigma and variables not used in φ\varphi [37]. Both properties have been extensively studied in modal logic; see [46] for a recent introduction and surveys of interpolation and its applications.

The traditional study of interpolation is qualitative: a logic either enjoys an interpolation property or it does not. While fundamental, this distinction provides little information about the prevalence of interpolation failure. A logic may fail interpolation because of a small collection of exceptional configurations, or failures may be widespread among its formulas. This raises a natural quantitative question:

How frequent are formulas, or pairs of formulas, for which interpolants exist?

In this paper, we initiate a systematic investigation of this question for quasi-normal propositional modal logics. We introduce densities of uniform and Craig interpolants by counting formulas modulo logical equivalence and study their asymptotic behaviour as the number of retained or forgotten propositional variables grows. We also investigate an alternative counting method that identifies formulas after existential quantification of the forgotten variables. Our results show that the choice of counting method matters. After existential quantification the densities can exhibit substantially different behaviour, revealing distinctions between modal logics that are invisible under ordinary counting.

To obtain a finite counting space, we fix two disjoint finite signatures σ\sigma and ρ\rho of retained and forgotten propositional variables, respectively, and a modal depth bound dd. At bounded depth, formulas over a finite signature form only finitely many equivalence classes. For locally tabular logics, the depth bound can be dropped.

Formulas of depth at most dd over σ∪ρ\sigma\cup\rho can be identified modulo logical equivalence with subsets of the finite set of complete (σ∪ρ,d)(\sigma\cup\rho,d)-types realised at distinguished worlds of Kripke models. We call these types (σ∪ρ,d)(\sigma\cup\rho,d)-atoms. We sample formulas uniformly modulo logical equivalence by choosing a subset of these atoms uniformly at random. Writing n=∣σ∣n=|\sigma| and m=∣ρ∣m=|\rho|, we define the uniform interpolation density

UnifInt⁡n,md\operatorname{UnifInt}^{d}_{n,m}

as the proportion of these formulas that admit a uniform interpolant over σ\sigma.

For Craig interpolation, we work with pairs of formulas φ,ψ\varphi,\psi over signatures σ∪ρ\sigma\cup\rho and σ∪ρ′\sigma\cup\rho', respectively, such that ∣ρ∣=∣ρ′∣|\rho|=|\rho'|. We consider pairs for which φ∧ψ\varphi\land\psi is inconsistent and ask whether their inconsistency can be witnessed by a formula over the common signature σ\sigma. This is equivalent to the usual formulation of Craig interpolation for valid implications. We define DCraign,md\mathrm{DCraig}^{d}_{n,m} as the proportion of such inconsistent pairs admitting a Craig interpolant.

A first observation of the paper is that these densities can be decomposed into densities over σ↑ρ\sigma^{\uparrow\rho}-cells, where a σ↑ρ\sigma^{\uparrow\rho}-cell is a set of (σ∪ρ,d)(\sigma\cup\rho,d)-atoms which cannot be distinguished, up to depth dd, using the language over σ\sigma alone. We prove that interpolation failure is local to cells and the global densities can be computed as products of local densities:

UnifIntn,md=∏CUnifIntC,DCraign,md=∏CDCraigC,\mathrm{UnifInt}^{d}_{n,m}=\prod_C\mathrm{UnifInt}_C,\qquad\mathrm{DCraig}^{d}_{n,m}=\prod_C\mathrm{DCraig}_C,

where CC ranges over the σ↑ρ\sigma^{\uparrow\rho}-cells. This basic cell reduction principle underlies all of our asymptotic results.

We begin with the regime in which ρ\rho is fixed and σ\sigma grows. Suppose that interpolation fails for σ0,ρ\sigma_0,\rho, and modal depth dd. For any σ⊇σ0\sigma\supseteq\sigma_0 of size nn, the original ‘obstruction’ can be copied into 2n2^n many distinct cells of the same size as the original one. Each copy contributes a fixed factor strictly below 1 to the product decomposition, giving

lim⁡n→∞UnifIntn,md=0if uniform interpolation fails,\lim_{n\to\infty}\mathrm{UnifInt}^{d}_{n,m}=0\quad\text{if uniform interpolation fails,}

and

lim⁡n→∞DCraign,md=0if Craig interpolation fails.\lim_{n\to\infty}\mathrm{DCraig}^{d}_{n,m}=0\quad\text{if Craig interpolation fails.}

The opposite regime, in which σ\sigma is fixed and ρ\rho grows, presents a different picture. As we show below, uniform interpolation admits a general convergence theorem in this regime, whereas the asymptotic behaviour of Craig interpolation remains open for arbitrary quasi-normal modal logics. For uniform interpolation, inside every cell there is a large family of atoms (2m2^m many) which cannot occur in any formula where uniform interpolation fails. Consequently the failure probability inside a cell is at most 2−2m2^{-2^m}. Since the number of cells depends only on σ\sigma, it follows that

lim⁡m→∞UnifIntn,md=1.\lim_{m\to\infty}\mathrm{UnifInt}^{d}_{n,m}=1.

For Craig interpolation, we focus on locally tabular quasi-normal modal logics, where no modal depth bound is needed. Within each cell CC, inconsistent pairs correspond to ordered bicliques in an incompatibility graph HCH_C on its atoms. Unlike in the uniform case, the large family of universally compatible atoms does not suffice to control the density, since large bicliques may still occur. To address this, we introduce the canonical profile of HCH_C as its coarsest quotient preserving and reflecting compatibility. Craig interpolation holds precisely when every cell has a singleton canonical profile. Relaxing this condition, we say that a logic LL has the uniformly bounded intra-cell incompatibility property (uniform BICIP) if the sizes of canonical profiles are bounded by a constant depending only on LL. We say that LL has BICIP if the bound may also depend on nn, but not on mm. Both properties imply that, for every fixed nn,

lim⁡m→∞DCraign,m=1.\lim_{m\to\infty}\mathrm{DCraig}_{n,m}=1.

We show that every tabular quasi-normal modal logic has uniform BICIP.

A natural alternative way of counting is to abstract from distinctions between formulas that disappear once the forgotten or non-shared variables are existentially quantified away. Thus, instead of counting the number of φ\varphi itself, we count the number of ∃p⃗.φ\exists\vec{p}.\varphi (up to logical equivalence). For Craig interpolation, the two components are treated separately, using ∃p⃗.φ\exists\vec{p}.\varphi and ∃p′⃗.ψ\exists\vec{p'}.\psi. We denote the corresponding densities by

UnifIntn,mΠ,dandDCraign,mΠ,d.\mathrm{UnifInt}^{\Pi,d}_{n,m}\qquad\text{and}\qquad\mathrm{DCraig}^{\Pi,d}_{n,m}.

We call these the uniform and Craig interpolation densities after existential quantification. Unlike ordinary modal equivalence, equivalence after existential quantification may depend on the chosen class of frames since two classes determining the same modal logic may induce different equivalence relations on existentially quantified formulas. Thus, counting up to equivalence after existential quantification depends not only on the logic but also on the chosen frame class. The natural choice is the class of all frames validating the logic, although we shall also consider well-motivated alternatives.

For this new counting measure, the cell decomposition remains valid, but the asymptotic behaviour can change substantially. When mm is fixed and nn grows, the previous asymptotic results continue to hold. The more interesting case is that of fixed nn and growing mm, where existential quantification can identify formulas that are distinct under ordinary modal equivalence.

Table 1 summarises the results for this regime. With the exception of the difference logic Diff (see below), our results on densities after existential quantification are shown for the class of all frames validating the logic. For tabular logics, there are only finitely many equivalence classes of existentially quantified formulas for any fixed nn. Hence, no substantive asymptotic analysis is required: the density sequences UnifIntn,mΠ\mathrm{UnifInt}^{\Pi}_{n,m} and DCraign,mΠ\mathrm{DCraig}^{\Pi}_{n,m} eventually stabilise as m→∞m \to\infty. This contrasts with their ordinary counterparts, which converge to 1. The difference arises because large families of distinct atoms that determine convergence under ordinary counting collapse to a single equivalence class after existential quantification.

logic / classordinary countingafter existential quantification
UnifIntn,m\mathrm{UnifInt}_{n,m}DCraign,m\mathrm{DCraig}_{n,m}UnifIntn,mΠ\mathrm{UnifInt}^{\Pi}_{n,m}DCraign,mΠ\mathrm{DCraig}^{\Pi}_{n,m}
arbitrary quasi-normal LL→1\to1?——
LL with BICIP→1\to1→1\to1bounded away from 0bounded away from 0
tabular LL→1\to1→1\to1stabilisesstabilises
Grz[Δ]\mathrm{Grz}[\Delta], Δ≥3\Delta\ge3→1\to1→1\to1→1\to1bounded away from 0
Diff→1\to1→1\to1→0∗\to0^{*}→0∗\to0^{*}

Table 1. Asymptotic behaviour of interpolant densities for fixed n=∣σ∣n = |\sigma| as m=∣ρ∣→∞m = |\rho| \to\infty. The superscript Π\Pi denotes counting modulo logical equivalence after existential quantification over the forgotten or non-shared variables. A question mark indicates that convergence to 1 is open. A dash indicates that no universal results holds. The results for Diff marked with * hold for the class of difference frames.

In case studies, we investigate the locally tabular logics Grz[Δ]\mathrm{Grz}[\Delta], for Δ≥1\Delta\ge1, and the difference logic Diff. The former are determined by finite partial orders of depth at most Δ\Delta. Craig interpolation fails for Grz[Δ]\mathrm{Grz}[\Delta] if and only if Δ≥3\Delta\ge3 [13 Chapter 8]. Counterexamples are, intuitively, rare as they require intricate incompatible arrangements of paths. By contrast, Diff, the logic of difference frames (W,≠)(W,\ne) [49, 40], admits straightforward counterexamples to Craig interpolation enforcing models of finite sizes [28].

This distinction is not directly visible under ordinary counting, where all the corresponding interpolation densities converge to 1. For Grz[Δ]\mathrm{Grz}[\Delta], convergence of the Craig interpolation density follows from BICIP (and even uniform BICIP when Δ≤3\Delta\le3). For Diff, it follows from a more involved analysis of quotients of incompatibility graphs.

The distinction becomes apparent after existential quantification. For Grz[Δ]\mathrm{Grz}[\Delta], the quantified uniform interpolation density still converges to 1, while the quantified Craig interpolation density remains bounded away from 0. By contrast, for Diff, both quantified densities converge to 0 over the class of difference frames. We note that not every frame validating Diff is a difference frame, but leave the asymptotic analysis over the full class of Diff-validating frames for future work.

Related work

Quantitative and asymptotic questions about logical properties have been studied along two broadly independent lines; the density of interpolant existence considered here sits at their intersection but does not seem to have been addressed before. Also related is work on the complexity of interpolant existence for logics without Craig or uniform interpolation and work on repairing Craig interpolation minimally.

Density of truth. Closest in method is the density of truth programme, which fixes a signature and asks for the fraction of length-nn formulas that are tautologies as n→∞n \to\infty [36, 50, 25, 27, 9, 10]. Of particular relevance, Kostrzycka and Zaionc compute the density of truth for the {→,□}\{\to,\Box\} fragments of S5 and S4 [26]. Related fragment computations include Dummett’s logic and monadic intermediate logics [23, 24]. In contrast to our approach, counting is not done modulo logical equivalence in this programme. In fact, since all tautologies are logically equivalent, this assumption would trivialise the density of truth as one would count only one tautology.

Zero-one laws. The older strand concerns randomness over structures rather than formulas. Glebskii et al. and Fagin established that every first-order sentence holds in almost all or almost no finite structures [16, 8]. In the modal setting, Halpern and Kapron proved zero-one laws for model validity in K, T, S4, S5 [19]; see also [30, 17, 20]. More recently Verbrugge established zero-one laws for provability logic and Grzegorczyk’s logic [47]. Our results are analogous in spirit to zero-one laws, although our probability spaces consist of formulas modulo logical equivalence rather than finite structures.

Deciding Interpolant Existence. The property whose density we measure has been studied qualitatively, as a decision problem, when Craig or uniform interpolation fails. For decidability of Craig interpolant existence, there are results for modal logics with nominals [2, 21], decidable fragments of FO [22], difference logic and weak K4 [28], and logics extending K4.3 [29]. Decidability of uniform interpolant existence has mainly been investigated in description logic [15, 31].

Repairing Craig Interpolation. Another way to deal with the failure of interpolation is to restore it by extending the expressive power of the language [1]. This raises the natural question of whether there is a minimal extension, in a suitable sense, that has interpolation, and if so, what it is. This question has been studied for, among others, modal logic with nominals [44], linear temporal logic [14], and fragments of first-order logic [45].

Preliminaries

We introduce basic notation for modal logic [3, 18]. Fix a countably infinite set PropProp of propositional variables. A signature τ\tau is a finite subset of PropProp. The language ML of modal formulas is built from propositional variables using ⊤\top, ¬\neg, ∧\land and the modal operator □\Box; we use standard connectives ⊥\bot, ∨\lor and →\to as abbreviations and set ◊φ:=¬□¬φ\Diamond\varphi:= \neg\Box\neg\varphi. We also use □≤d\Box^{\le d} defined by taking ⋀i=0d□iφ\bigwedge_{i=0}^{d}\Box^{i}\varphi, where □i\Box^{i} stands for ii operators □\Box. We write sig⁡(φ)\operatorname{sig}(\varphi) for the signature of φ\varphi, the finite set of propositional variables occurring in φ\varphi, and md⁡(φ)\operatorname{md}(\varphi) for the modal depth of φ\varphi, the maximal nesting of □\Box. For a signature τ⊆Prop\tau\subseteq Prop and a depth d≥0d \ge0, we put

MLτd:={φ∈ML∣sig⁡(φ)⊆τ, md⁡(φ)≤d}andMLτ:=⋃d≥0MLτd.\mathrm{ML}_{\tau}^{d}:=\{\varphi\in\mathrm{ML}\mid\operatorname{sig}(\varphi)\subseteq\tau,\ \operatorname{md}(\varphi)\le d\}\quad\text{and}\quad\mathrm{ML}_{\tau}:=\bigcup_{d\ge0}\mathrm{ML}_{\tau}^{d}.

Modal formulas are interpreted in Kripke frames, or simply frames. A frame is a triple F=(W,R,A)\mathfrak{F}=(W,R,A), where WW is a nonempty set of worlds, R⊆W×WR\subseteq W\times W is a binary accessibility relation on WW, and A⊆2WA\subseteq2^{W} is a set of admissible valuations on WW, closed under the Boolean operations ∪\cup, ∩\cap and ∼\mathord{\sim} and defined by taking F(U)={w∈W∣w′∈U, for all w′∈W with wRw′}F(U)=\{w\in W\mid w' \in U,\ \text{for all }w'\in W\text{ with }wRw'\}. If every set of worlds is admissible (that is, A=2WA=2^{W}), then we omit AA and write (W,R)(W,R). A model based on F\mathfrak{F} is a pair M=(F,V)\mathfrak{M}=(\mathfrak{F},V) with a valuation V:Prop→AV:Prop\to A. A pointed model is a pair of the form (M,w)(\mathfrak{M},w) with w∈Ww\in W. The satisfaction relation between pointed models (M,w)(\mathfrak{M},w) and formulas is defined as follows:

  • M,w⊩p\mathfrak{M},w \Vdash p iff w∈V(p)w\in V(p);

  • M,w⊩⊤\mathfrak{M},w \Vdash\top;

  • M,w⊩¬φ\mathfrak{M},w \Vdash\neg\varphi iff M,w⊮φ\mathfrak{M},w \nVdash\varphi;

  • M,w⊨φ∧ψ\mathcal{M}, w \models\varphi\land\psi iff M,w⊨φ\mathcal{M}, w \models\varphi and M,w⊨ψ\mathcal{M}, w \models\psi;

  • M,w⊨□φ\mathcal{M}, w \models\Box\varphi iff w∈F({w′∈W∣M,w′⊨φ})w \in F(\{w' \in W \mid\mathcal{M}, w' \models\varphi\}).

A formula φ\varphi is valid in a pointed frame (F,w)(\mathfrak{F}, w), written F,w⊨φ\mathfrak{F}, w \models\varphi, if M,w⊨φ\mathcal{M}, w \models\varphi for every model M\mathcal{M} based on F\mathfrak{F}. For a class K\mathcal{K} of pointed frames,

References

  1. [1]Carlos Areces, Patrick Blackburn, and Maarten Marx. Repairing the interpolation theorem in quantified modal logic. Ann. Pure Appl. Log., 124(1-3):287–299, 2003.DOI
  2. [2]Alessandro Artale, Jean Christoph Jung, Andrea Mazzullo, Ana Ozaki, and Frank Wolter. Living without Beth and Craig: Definitions and interpolants in description and modal logics with nominals and role inclusions. ACM Trans. Comput. Log., 24(4):34:1–34:51, 2023.
  3. [3]Alexander V. Chagrov and Michael Zakharyaschev. Modal Logic, volume 35 of Oxford logic guides. Oxford University Press, 1997.
  4. [4]Chen Chung Chang and H. Jerome Keisler. Model Theory. Elsevier, 1998.
  5. [5]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
  6. [6]Giovanna D’Agostino and Marco Hollenberg. Uniform interpolation, automata and the modal μ-calculus. In Proceedings of the 1st Workshop on Advances in Modal Logic, AiML-1, pages 73–84. CSLI Publications, 1996.
  7. [7]Maarten de Rijke. The modal logic of inequality. J. Symb. Log., 57(2):566–584, 1992.DOI
  8. [8]Ronald Fagin. Probabilities on finite models. The Journal of Symbolic Logic, 41(1):50–58, 1976.DOI
  9. [9]Hervé Fournier, Danièle Gardy, Antoine Genitrini, and Marek Zaionc. Classical and intuitionistic logic are asymptotically identical. In Computer Science Logic (CSL 2007), volume 4646 of Lecture Notes in Computer Science. Springer, 2007.DOI
  10. [10]Hervé Fournier, Danièle Gardy, Antoine Genitrini, and Marek Zaionc. Tautologies over implication with negative literals. Mathematical Logic Quarterly, 56(4):388–396, 2010.DOI
  11. [11]Tim French. Bisimulation quantifiers for modal logics. PhD thesis, The University of Western Australia, 2006.
  12. [12]Wesley Fussner. Interpolation in non-classical logics. In Balder ten Cate, Jean Christoph Jung, Patrick Koopmann, Christoph Wernhard, and Frank Wolter, editors, Theory and Applications of Craig Interpolation, pages 69–100. Ubiquity Press, 2026.arxiv.org/abs/2512.01600
  13. [13]Dov M. Gabbay and Larisa Maksimova. Interpolation and Definability: Modal and Intuitionistic Logics. Oxford University Press, 2005.
  14. [14]Amélie Gheerbrant and Balder ten Cate. Craig interpolation for linear temporal languages. In Erich Grädel and Reinhard Kahle, editors, Computer Science Logic, 23rd international Workshop, CSL 2009, 18th Annual Conference of the EACSL, Coimbra, Portugal, September 7-11, 2009. Proceedings, volume 5771 of Lecture Notes in Computer Science, pages 287–301. Springer, 2009.DOI
  15. [15]Silvio Ghilardi, Carsten Lutz, and Frank Wolter. Did I damage my ontology? A case for conservative extensions in description logics. In Proceedings, Tenth International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the United Kingdom, June 2-5, 2006, pages 187–197. AAAI Press, 2006.
  16. [16]Yuri V. Glebskij, Dmitry I. Kogan, Mikhail I. Liogon’kii, and Vladimir A. Talanov. Volume and fraction of satisfiability of formulas of the lower predicate calculus. Kibernetika, (2):17–27, 1969.
  17. [17]Valentin Goranko and Bruce Kapron. The modal logic of the countable random frame. Archive for Mathematical Logic, 42(3):221–243, 2003.DOI
  18. [18]Valentin Goranko and Martin Otto. Model theory of modal logic. In Patrick Blackburn, Johan van Benthem, and Frank Wolter, editors, Handbook of Modal Logic, volume 3 of Studies in logic and practical reasoning, pages 249–329. Elsevier, 2007.
  19. [19]Joseph Y. Halpern and Bruce Kapron. Zero-one laws for modal logic. Annals of Pure and Applied Logic, 69(2–3):157–193, 1994.
  20. [20]Joseph Y. Halpern and Bruce M. Kapron. Erratum to “Zero-one laws for modal logic”. Annals of Pure and Applied Logic, 121(2–3):281–283, 2003.
  21. [21]Jean Christoph Jung, Jedrzej Kolodziejskij, and Frank Wolter. Computation and size of interpolants for hybrid modal logics. In Claudia Faggian and Joost-Pieter Katoen, editors, 41st Annual Symposium on Logic in Computer Science, LICS 2026, Lisbon, Portugal, July 20–23, 2026, volume 380 of LIPICs, pages 60:1–60:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
  22. [22]Jean Christoph Jung and Frank Wolter. Living without Beth and Craig: Definitions and interpolants in the guarded and two-variable fragments. In Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, pages 1–14. IEEE, 2021.
  23. [23]Zofia Kostrzycka. On the density of truth in Dummett’s logic. Bulletin of the Section of Logic, 32(1–2):43–55, 2003.
  24. [24]Zofia Kostrzycka. The density of truth in monadic fragments of some intermediate logics. Journal of Logic, Language and Information, 16:283–302, 2007.
  25. [25]Zofia Kostrzycka and Marek Zaionc. Statistics of intuitionistic versus classical logics. Studia Logica, 76(3):307–328, 2004.DOI
  26. [26]Zofia Kostrzycka and Marek Zaionc. Density of truth in modal logics. In Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings, 2006. Discrete Mathematics and Theoretical Computer Science.DOI
  27. [27]Zofia Kostrzycka and Marek Zaionc. Asymptotic densities in logic and type theory. Studia Logica, 88(3):385–403, 2008.DOI
  28. [28]Agi Kurucz, Frank Wolter, and Michael Zakharyaschev. The interpolant existence problem for weak K4 and difference logic. In Agata Ciabattoni, David Gabelia, and Igor Sedlár, editors, Advances in Modal Logic, AiML 2024, Prague, Czech Republic, August 19–23, 2024, pages 465–484. College Publications, 2024.
  29. [29]Agi Kurucz, Frank Wolter, and Michael Zakharyaschev. A non-uniform view of Craig interpolation in modal logics with linear frames. The Journal of Symbolic Logic, 91(3):1037–1088, 2026.
  30. [30]Jean-Marie Le Bars. The 0-1 law fails for frame satisfiability of propositional modal logic. In 17th Annual IEEE Symposium on Logic in Computer Science (LICS 2002). IEEE Computer Society, 2002.
  31. [31]Carsten Lutz, Inanç Seylan, and Frank Wolter. An automata-theoretic approach to uniform interpolation and approximation in the description logic ℒℒ. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning, KR 2012. AAAI Press, 2012.
  32. [32]Carsten Lutz and Frank Wolter. Foundations for uniform interpolation and forgetting in expressive description logics. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011, pages 989–995. IJCAI/AAAI, 2011.
  33. [33]Larisa L. Maksimova. Craig’s theorem in superintuitionistic logics and amalgamable varieties of pseudo-Boolean algebras. Algebra and Logic, 16:427–455, 1978.DOI
  34. [34]Larisa L. Maksimova. Interpolation theorems in modal logics and amalgamable varieties of topological Boolean algebras. Algebra and Logic, 18:348–370, 1980.DOI
  35. [35]Larisa L. Maksimova. Interpolation theorems in modal logics. Sufficient conditions. Algebra and Logic, 19(2):120–132, 1981.DOI
  36. [36]Małgorzata Moczurad, Jerzy Tyszkiewicz, and Marek Zaionc. Statistical properties of simple types. Mathematical Structures in Computer Science, 10:575–594, 2000.DOI
  37. [37]Andrew M. Pitts. On an interpretation of second order quantification in first order intuitionistic propositional logic. J. Symb. Log., 57(1):33–52, 1992.DOI
  38. [38]Simon Santschi and Niels C. Vooijs. Interpolation above S4. CoRR, abs/2604.22020, 2026.arxiv.org/abs/2604.22020
  39. [39]Krister Segerberg. An Essay in Classical Modal Logic. Number 13 in Filosofiska Studier. Uppsala Universitet, 1971.
  40. [40]Krister Segerberg. A note on the logic of elsewhere. Theoria, 46(2-3):183–187, 1980.DOI
  41. [41]Ilya B. Shapirovsky. Sufficient conditions for local tabularity of a polymodal logic. J. Symb. Log., 90(2):655–680, 2025.DOI
  42. [42]Ilya B. Shapirovsky. Generalizations of the finite height criterion for local tabularity. CoRR, abs/2509.17612, 2026.arxiv.org/abs/2509.17612
  43. [43]Valentin B. Shehtman. Bisimulation games and locally tabular logics. Russian Mathematical Surveys, 71(5):979–981, 2016.DOI
  44. [44]Balder ten Cate. Interpolation for extended modal languages. J. Symb. Log., 70(1):223–234, 2005.
  45. [45]Balder ten Cate and Jesse Comer. Craig interpolation for decidable first-order fragments. Log. Methods Comput. Sci., 21(3), 2025.
  46. [46]Balder ten Cate, Jean Christoph Jung, Patrick Koopmann, Christoph Wernhard, and Frank Wolter, editors. Theory and Applications of Craig Interpolation. Ubiquity Press, September 2026. Open Access.DOI
  47. [47]Rineke Verbrugge. Zero-one laws for provability logic: axiomatizing validity in almost all models and almost all frames. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021). IEEE, 2021.arxiv.org/abs/2102.05947
  48. [48]Albert Visser. Uniform interpolation and layered bisimulation. In Gödel’96: Logical foundations of mathematics, computer science and physics–Kurt Gödel’s legacy, pages 139–164. Association for Symbolic Logic, 1996.
  49. [49]Georg Henrik von Wright. A modal logic of place. In The philosophy of Nicolaas Rescher, pages 65–73. Dordrecht, 1979.
  50. [50]Marek Zaionc. Probability distribution for simple tautologies. Theoretical Computer Science, 355(2):243–260, 2006.DOI

Paper details

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

views · 3

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