4 papers
Boolean Dependence Logic and Partially-Ordered Connectives
Johannes Ebbing, Lauri Hella, Peter Lohmann +1
We introduce a new variant of dependence logic called Boolean dependence logic. In Boolean dependence logic dependence atoms are of the type =(x_1,...,x_n,α), where αis a Boolean v…
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…