News

• Die Vorträge finden im Raum 5056 (2356|056) (Seminarraum am AH V) statt.
• Die von der Fachgruppe Informatik verfassten ethischen Richtlinien für das Verfassen wissenschaftlicher Arbeiten sind hier zu finden und gelten selbstverständlich auch für dieses Seminar.

Registration

Students with a subject in mathematics can apply by writing an email to seminar [AT] logic.rwth-aachen.de including their name, immatriculation no., subject of studies, no. of semesters of studies, and information about relevant modules they have passed (especially lectures from our group).

Organisation

Die Veranstaltung wird als Blockseminar angeboten, die Vorträge werden am Ende des Semesters wahlweise auf deutsch oder englisch gehalten.

Deadlines

22. Mai	Gliederung
19. Juni	Ausarbeitung
spätestens 13. Juli	Folien
13. August	Vorträge

Schedule

Donnerstag, 13. August
10:00	–	10:30	Lena Vollbach	LFP = IFP
10:30	–	11:00	Mehri Bagherihamaneh	Bounded-Variable Fixpoint Queries are PSPACE-Complete
11:15	–	11:45	Carolin Tidau	The Expressive Equivalence of LFP and PFP
11:45	–	12:15	Matthias Voit	Monadic Least Fixed-Point Logic and its Two-Variable Fragments
14:00	–	14:30	Markus Baumeister	Strictness of the Alternation Hierachy of the Modal mu-Calculus
14:30	–	15:00	Oliver Major	Inflationary Fixed Points in Modal Logic

Content

Fixed-point logics are of fundamental importance in many branches of logic and computer science, including finite model theory, verification, knowledge representation, complexity theory, and databases. They extend a basic logical formalism (such as first-order logic, propositional modal logic, or conjunctive queries) by the possibility to define fixed-points of relational operators. Fixed-point logic come in many incarnations and variations, depending on the kind of relational operators that are used, on the kind of fixed-points (least and greatest fixed points, inflationary and deflationary fixed points, partial fixed points, simultaneous inductions, etc.,) and on the combination and interaction with other logical operators.

In finite model theory, fixed-point logics play a central role since they capture recursion and unbounded iteration in a natural and powerful way, and are of fundamental importance in the quest of logics that capture complexity classes. In database theory, query languages based on fixed-points, such as Datalog and its extensions, are of interest since they allow to define queries that are not expressible in basic languages like SQL. The modal mu-calculus is an important formalism for the specification and verification and encompasses most of the commonly used modal and temporal logics used in that area. There also is a very close and important relationship of fixed-point logic with the theory of infinite games.

In the seminar, we shall study the structure, the model-theoretic properties, and the expressive power of different variants of fixed-point logic, and explore algorithmic problems that arise in the application of such formalisms in different areas of logic and computer science.

Topics

Thema	Vortragende(r)	Betreuer(in)
LFP = IFP	Lena Vollbach	Wied Pakusa
Monadic Least Fixed-Point Logic and its Two-Variable Fragments	Matthias Voit	Wied Pakusa
The Expressive Equivalence of LFP and PFP	Carolin Tidau	Svenja Schalthöfer
Bounded-Variable Fixpoint Queries are PSPACE-Complete	Mehri Bagherihamaneh	Faried Abu Zaid
Inflationary Fixed Points in Modal Logic	Oliver Major	Faried Abu Zaid
Strictness of the Alternation Hierachy of the Modal mu-Calculus	Markus Baumeister	Frederic Reinhardt

Classification

• Informatik (B.Sc.)/Seminar Informatik
• Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
• Informatik (M.Sc.)/Seminar Theoretische Informatik
• Mathematik (M.Sc.)/Seminar: Logik, Komplexität, Spiele (Reine Mathematik)
• Informatik (S II)
• Mathematik (S II)/Hauptstudium/Modul Algebra
• Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Prerequisites

• Module Mathematical Logic
• for B.Sc. Computer Science: Module "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Contact

Erich Grädel, Faried Abu Zaid, Wied Pakusa, Svenja Schalthöfer, Frederic Reinhardt