4 papers · 1 filter
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…
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…
A SUBSET-SUM Characterisation of the A-Hierarchy
Jan Gutleben, Arne Meier
The A-hierarchy is a parametric analogue of the polynomial hierarchy in the context of paramterised complexity theory. We give a new characterisation of the A-hierarchy in terms of…
Logics with probabilistic team semantics and the Boolean negation
Miika Hannula, Minna Hirvonen, Juha Kontinen +3
We study the expressivity and the complexity of various logics in probabilistic team semantics with the Boolean negation. In particular, we study the extension of probabilistic ind…