21 citations · 116 across the 38 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
cs.LO2012★ 7 cited
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…
math.LO2012★ 4 cited
Axiomatizing first order consequences in dependence logic
Juha Kontinen, Jouko Väänänen
Dependence logic, introduced in [8], cannot be axiomatized. However, first-order consequences of dependence logic sentences can be axiomatized, and this is what we shall do in this…
math.LO2012★ 2 cited
Characterizing Quantifier Extensions of Dependence Logic
Fredrik Engström, Juha Kontinen
We characterize the expressive power of extensions of Dependence Logic and Independence Logic by monotone generalized quantifiers in terms of quantifier extensions of existential s…