7 citations · 9 across the 3 of their papers we have counts for
3 papers · 1 filter
A Fragment of Dependence Logic Capturing Polynomial Time
Johannes Ebbing, Juha Kontinen, Julian-Steffen Müller +1
In this paper we study the expressive power of Horn-formulae in dependence logic and show that they can express NP-complete problems. Therefore we define an even smaller fragment D…
Dependence logic with a majority quantifier
Arnaud Durand, Johannes Ebbing, Juha Kontinen +1
We study the extension of dependence logic D by a majority quantifier M over finite structures. We show that the resulting logic is equi-expressive with the extension of second-ord…
Complexity of Model Checking for Modal Dependence Logic
Johannes Ebbing, Peter Lohmann
Modal dependence logic (MDL) was introduced recently by Väänänen. It enhances the basic modal language by an operator =(). For propositional variables p_1,...,p_n the atomic formul…