Die Informatik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Verwaltung des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Informatik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Mathematik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Universität Bremen
Zeige Digitale Medien-Format Pdf_icon Systems Engineering-Format Pdf_icon Informatik-Format Pdf_icon Wirtschaftsinformatik-Format Pdf_icon

Informatik-Ansicht

Finite and Algorithmic Model Theory


Finite and Algorithmic Model Theory
Modulnummer
03-ME-605.21
Master
Pflicht/Wahl
Wahl Basis Ergänzung
Sonderfall
Zugeordnet zu Masterprofil
Basis Ergänzung
Sicherheit und Qualität
KI, Kognition, Robotik
Digitale Medien und Interaktion
Modulbereich : (keine Angabe)
Modulteilbereich : 605 Logik
Anzahl der SWS
V UE K S Prak. Proj.
2 2 0 0 0 0 4
Kreditpunkte : 6 Turnus

I.d.R. angeboten in jedem zweiten Wintersemester

Formale Voraussetzungen : Keine
Inhaltliche Voraussetzungen : Theoretische Informatik 1 + 2
Vorgesehenes Semester : ab 1. Semester
Sprache : Englisch
Ziele :
  • Die Studierenden erlangen Kenntnisse über grundlegende und fortgeschrittene Konzepte aus der Modelltheorie und endlichen Modelltheorie.
  • Die Studierenden erlangen Kenntnisse über grundlegende Konzepte aus der Komplexitätstheorie.
  • Die Studierenden sind in der Lage, komplexe Aufgaben in Gruppen und selbstständig zu lösen.
  • Die Studierenden können erarbeitete Ergebnisse präzise und prägnant präsentieren.
  • Die Studierenden sind in der Lage, englische Fachtexte zu verstehen und ihre Ergebnisse auf Englisch zu kommunizieren.
Inhalte :

Finite model theory, that is, the model theory of nite structures, has its roots in classical model theory. However, its systematic development was strongly influenced by questions of complexity theory and database theory. In this course we are going to cover the basics of classical first-order and second-order model theory. When restricting to finite structures, the essential theorems, most notably the compactness theorem for first-order logic, fail. We will study the game theoretic methods of Ehrenfeucht and Fraisse that survive and even gain in power over finite models. We then turn our attention to descriptive complexity with the aim to provide machine independent descriptions of important complexity classes. For example, the question whether PTime = PSpace in this theory amounts to the question whether least fixed-point logic has the same expressive power as partial fixed-point logic over finite structures. Finally, we will study locality properties of first-order logic with applications to the algorithmic evaluation and enumeration of queries in relational databases and graphs.

Contents:

  • Basic first-order model theory, compactness
  • Game characterisations of first-order logic, second-order logic and fixed-point logics
  • Game based approaches to model-checking over finite structures
  • Basic complexity theory and descriptive complexity
  • Model-checking and query evaluation and enumeration over relational databases
Unterlagen (Skripte, Literatur, Programme usw.) :
  • Vorlesungsskript
  • Erich Grädel et al. Finite Model Theory and its applications. Springer, 2007.
  • Leonid Libkin. Elements of nite model theory. Springer, 2013.
  • Heinz-Dieter Ebbinghaus and Jörg Flum. Finite model theory. Springer, 2005.
Form der Prüfung : i.d.R. Bearbeitung von Übungsaufgaben und Fachgespräch oder mündliche Prüfung
Arbeitsaufwand
Präsenz 56
Übungen + Prüfungsvorbereitung 124
Summe 180 h
Lehrende: Prof. Dr. Sebastian Siebertz Verantwortlich Prof. Dr. Sebastian Siebertz
Zurück

Zeige Digitale Medien-Format Pdf_icon Systems Engineering-Format Pdf_icon Informatik-Format Pdf_icon Wirtschaftsinformatik-Format Pdf_icon