Dependence logic, spring 2011
Dependence logic, spring 2011
Lecturer
Scope
5 cu.
Type
Advanced studies
Description
Dependence logic adds the concept of dependence to first-order logic by the means of new atomic dependence formulas =(x_1,…,x_n,y),
meaning that the values of the variables x_1,…,x_n completely determine the values of the variable y. Dependence logic bases its semantics in the concept of a set X of assignments satisfying a formula (rather than an individual assignment satisfying a formula, as in first-order logic).
This course discusses dependence logic in the context of finite structures. Over finite structures, various extensions of first-order logic have been studied. It is known that many of these logics correspond to interesting complexity classes in computational complexity theory. In this course we discuss dependence logic from the complexity theoretic point of view. For example, we will show that dependence logic corresponds exactly to the complexity class nondeterministic polynomial time (NP).
Prerequisites
Mathematical logic (Matemaattinen logiikka) and finite model theory (Äärellisten mallien teoria).
Lectures
Weeks 11-18, Monday 12-14 and Thursday 12-14 in room B321.
Easter holiday 21.-27.4.
Contents of lectures
Exam
The Exam will be held on Wednesday 11.5 at 12-16 in room B321.
Bibliography
- Jouko Väänänen: Dependence Logic.
A New Approach to Independence Friendly Logic.
Series: London Mathematical Society Student Texts (No. 70).
- Jarmo Kontinen: Coherence and Complexity in Fragments of Dependence Logic.
Doctoral thesis, University of Amsterdam, 2010. (available at http://www.illc.uva.nl/Publications/reportlist.php?Series=DS)
Registration
Did you forget to register? What to do.
Exercises
Exercise groups
Group | Day | Time | Place | Instructor |
|---|---|---|---|---|
1. | Tuesday | 10-12 | C130 | Juha Kontinen |