Introduction to Finite Model Theory (FMT)7.5 ECTS
(englische Bezeichnung: Introduction to Finite Model Theory)
(Prüfungsordnungsmodul: Introduction to Finite Model Theory)

Lehrveranstaltungen:

• • Introduction to Finite Model Theory
    (Vorlesung mit Übung, 4 SWS, Tadeusz Litak, Mi, 14:15 - 15:45, 00.131-128; Do, 16:15 - 17:45, 01.255-128; Do, 14.15-15.45 Uhr im Raum 00.131-128, Cauerstraße 11)

Inhalt:

We will discuss basic results of finite model theory. This module can be seen as a natural continuation of GLoIn.

Lernziele und Kompetenzen:

Wissen

The students will learn basic notions and results of finite model theory.

Verstehen

The students will be able to summarize and prove major results of finite model theory and explain the deep difference between finite and infinite model theory, by using 0-1 laws or by showing the failure of most preservation theorems.

Anwenden

The students will be able to use basic tools of finite model theory such as Ehrenfeucht-Fraisse games or Herbrand structures.
The students will use preservation theorems of Rosen or Rossman to characterize expressive power of logics over finite structures.

Analysieren

The students will be able to determine, e.g., whether a given query is expressible over all finite models (or restricted subclasses of structures) in a chosen language.

Evaluieren (Beurteilen)

The best students, having gained a deep understanding of finite model theory, will be able to examine and evaluate choices involved in the design of query languages, with particular attention to the criterion of expressive completeness and contrasting expressive power of a given language with its computational complexity.

Erschaffen

Making the right design choices is an important skill whenever the need arises to develop a new domain-specific language.

Literatur:

• Leonid Libkin, Elements of Finite Model Theory, Springer 2012

• Heinz-Dieter Ebbinghaus, Jörg Flum, Finite Model Theory, Springer 1995

• Phokion Kolaitis. The Expressive Power of Logics on Finite Models, in Finite Model Theory and its Applications, EATCS Series: Texts in Theoretical Computer Science, Springer 2007

Supplementary reading on logic and classical (unrestricted) model theory

• Herbert B. Enderton. A Mathematical Introduction to Logic (1 ed. 1972). Academic Press Second edition, 2001. ISBN 978-0-12-238452-3

• Wilfrid Hodges. Model theory, Cambridge University Press, Cambridge 1993, 772pp.

Weitere Informationen:

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Informatik (Master of Science)
   (Po-Vers. 2010 | TechFak | Informatik (Master of Science) | Wahlpflichtbereich | Säule der theoretisch orientierten Vertiefungsrichtungen | Vertiefungsrichtung Theoretische Informatik | Introduction to Finite Model Theory)

Studien-/Prüfungsleistungen:

Introduction to Finite Model Theory (Prüfungsnummer: 46411)

(englischer Titel: Introduction to Finite Model Theory)

Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet, 7.5 ECTS

Anteil an der Berechnung der Modulnote: 100.0 %

weitere Erläuterungen:
Die Modulnote setzt sich zu 50% aus dem Ergebnis einer 30-minütigen mündlichen Prüfung am Semesterende und zu 50% aus der Note für die Bearbeitung von regelmäßig gestellten Übungsaufgaben zusammen.

Prüfungssprache: Englisch

Erstablegung: WS 2019/2020, 1. Wdh.: SS 2020

1. Prüfer:

Tadeusz Litak