Date: Wed 31 Gen
Time: 15.00
Place: room 214

Speaker: Yuri Gurevich (Univ. of Michigan)
Title: Finite Model Theory
Reference: Egidio Astesiano e Eugenio Moggi

Abstract. Classical logic was developed to confront the Infinite, but in computer science applications it is often meaningful to restrict attention to finite structures. Think about databases for example. This phenomenon gave impetus to the development of finite model theory and various alternatives to classical logic. Finite model theory happens to be quite different from classical model theory; complexity theory is often a useful guide. We survey these developments including a recent twist a la Hegel (thesis, antithesis, synthesis) concerning so-called metafinite structures.