37 citations · 80 across the 29 of their papers we have counts for
39 papers
Parameterized Enumeration of Minimal Defensive Alliances
Henning Fernau, Kevin Mann, Arne Meier +1
In this paper, we consider the complexity of enumerating inclusion minimal defensive alliances. We present a polynomial-delay algorithm on graphs with maximum degree 5. We compleme…
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…
Parameterized Complexity of Weighted Team Definability
Juha Kontinen, Yasir Mahmood, Arne Meier +1
In this article, we study the complexity of weighted team definability for logics with team semantics. This problem is a natural analogue of one of the most studied problems in par…