Wed 31 Gen
Yuri Gurevich (Univ. of Michigan)
Finite Model Theory
Egidio Astesiano e Eugenio Moggi
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.