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 Wirtschaftsinformatik-Format Pdf_icon Digitale Medien-Format Pdf_icon Informatik-Format Pdf_icon Systems Engineering-Format Pdf_icon

Digitale Medien-Ansicht

Modulnummer
Modulbezeichnung
Finite and Algorithmic Model Theory
Titel (englisch)
Finite and Algorithmic Model Theory
Pflicht/Wahl
Pflicht
Erklärung
CP
6
Berechnung des Workloads
Turnus
I.d.R. angeboten in jedem zweiten Wintersemester
Dauer
ein Semester
Form
2 SWS L, 2 SWS T
Prüfung
i.d.R. Bearbeitung von Übungsaufgaben und Fachgespräch oder mündliche Prüfung
Anforderungen
Keine
Lernziele
  • 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.
Lerninhalte

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
Quellen
  • 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.
Sprache
Englisch
Bemerkung
Zuletzt geändert
2019-08-20 14:35:29 UTC
Zurück

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