Tabular modal logics admit propositionally sized interpolants and strongest implicates iff NP ⊆ P/poly, while non-tabular ones require exponential size unconditionally.
Mechanised uniform interpolation for modal logics k, gl, and isl
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.LO 1years
2025 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
The Size of Interpolants in Modal Logics
Tabular modal logics admit propositionally sized interpolants and strongest implicates iff NP ⊆ P/poly, while non-tabular ones require exponential size unconditionally.