2 papers
cs.LO2026
Modal Fragments
Nick Bezhanishvili, Balder ten Cate, Arunavo Ganguly +1
We survey systematic approaches to basis-restricted fragments of propositional logic and modal logics, with an emphasis on how expressive power and computational complexity depend…
cs.LO2025
When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
Andreas Krebs, Arne Meier
Hemaspaandra~et~al.~[JCSS 2010] conjectured that satisfiability for multi-modal logic restricted to the connectives XOR and 1, over frame classes T, S4, and S5, is solvable in poly…