Title: Logics over finite structures

Abstract:  Finite model theory studies logics over finite structures. A central question for a logic \mathcal{L} is to determine which classes of finite structures can be axiomatized by \mathcal{L}-sentences. On the other hand, a fundamental task in  computational complexity theory  is to classify problems with respect to resources such  as time and working space needed to solve them. By a seminal result of Fagin (1974), a class of finite structures K is axiomatizable in existential second-order logic iff K  can be decided  by a nondeterministic Turing machine in polynomial time.  Fagin's theorem has led to a large body of results and today complexity theory and logic are intimately connected.  
In the first part of my talk I will give a brief introduction to finite model theory.   In the second part I will turn to consider logics in team semantics and explain how they relate to the logics discussed in the first part of the talk.