Skip to main content

Complexity results for dependence logic

Juha Kontinen ( Dept. of Mathematics and Statistics, University of Helsinki )

Dependence Logic is a new logic that incorporates the concept of dependence into first-order logic. It was introduced by Jouko Väänänen in his monograph "Dependence Logic" in 2007. The expressive power of dependence logic coincides with that of existential second-order logic. We give a general introduction to dependence logic and then review some recent results regarding the expressive power and complexity of certain fragments and extensions of dependence logic.

Share this: