Finite Model Theory

Finite Model Theory (FMT) is a subarea of Model Theory (MT). MT is the branch of mathematical logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). FMT is a restriction of MT to finite structures, such as finite graphs or strings. Since many central theorems of MT do not hold when restricted to finite structures, FMT is quite different from MT in methods and application areas. FMT has become an "unusually effective" instrument in computer science, for example in database theory, model checking or for gaining new perspectives on computational complexity. The three main areas of FMT are presented here: Expressive Power of Languages, Descriptive Complexity, and Random Structures. But first the results fundamental for all areas are introduced on the level of first order languages. Finite model theory Basics Why? (Motivation) What is it? (Definition and Background) Why is it special? (... compared to 'common' Model Theory) What is it about? (Typical Logics and Structures studied) What is required? (Preliminaries) What to start with? (Basic Concepts) Ehrenfeucht-Fraisse-Games for FO The Problem (Expressibility of Properties) The Idea I (Fraisse's Theorem) The Idea II (Ehrenfeucht's Games) The Tool (Ehrenfeucht-Fraisse-Method) Some Utilities (Localities) Some Solutions (for some Structures) Complexity? Expressive Power of Languages Typical problem: Given a finite graph, can the property of being an acyclic be expressed in a first order language? Descriptive Complexity Random Structures Mathematical logic University level mathematics books F 25% __NOTOC__ __NOEDITSECTION__