← 研踪 PaperTrailarXiv:2611.26091 · v1
The Density of Interpolants in Modal Logic: First Results
首次提交 2026-11-19 21:29
版本更新 2026-11-19 21:29
雷达观测 2026-11-20 16:53
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-19 21:29 · 最新观测版本
The Density of Interpolants in Modal Logic: First Results
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.
查看此版本解读 →查看此版本原文 ↗