Aktuelles

Das Seminar wird als Blockseminar angeboten. Die Vorträge finden im Seminarraum des Lehrstuhl statt (Raum 4116, E1, Ahornstr. 55) und können wahlweise auf Deutsch oder Englisch gehalten werden.

Zeitplan

07.11.	Gliederung
05.12.	1. Version Ausarbeitung
02.01.	finale Version Ausarbeitung
09.01.	Folien
23.01. und 24.01.	Vorträge

Einführungsliteratur

Folgende Übersichtsartikel sind für alle Themen als Einführungsliteratur empfohlen: [G08, K09, GK11]

Programm

Montag, 23. Januar
10:00	–	10:30	Marko van Treeck	Fixed-parameter tractability
10:35	–	11:05	Oliver Feith	Hierarchien in der parametrisierten Komplexitätstheorie
11:10	–	11:40	Lukas Rodenbüsch	Varianten von monadischer Logik zweiter Stufe
13:00	–	13:30	Valentin Seiler	Baumweite
13:35	–	14:05	Dimitri Rusin	Der Satz von Courcelle
14:10	–	14:40	Johannes Rueben	Cliquenweite
14:45	–	15:15	Jan-Frederik Konopka	Lokalität von FO und der Satz von Seese
Dienstag, 24. Januar
11:00	–	11:30	Robert Lipp	FO-Eigenschaften von Strukturen mit lokaler Baumzerlegung
13:00	–	13:30	Daniel Steenebrügge	FO-Eigenschaften von nirgends dichten Graphen (1)
13:35	–	14:05	Nikolai von der Burg	FO-Eigenschaften von nirgends dichten Graphen (2)
14:10	–	14:40	Katrin Dannert	FO-Eigenschaften von nirgends dichten Graphen (3)
14:45	–	15:15	Yannic Rohde	FO-Eigenschaften endlicher abelscher Gruppen entscheiden

Themen

Thema	Vortragende(r)	Betreuer(in)	Literatur
Fixed-parameter tractability	Marko van Treeck	Matthias Hoelzel	[FG06]
Hierarchien in der parametrisierten Komplexitätstheorie	Oliver Feith	Svenja Schalthöfer	[FG06]
Varianten von monadischer Logik zweiter Stufe	Lukas Rodenbüsch	Svenja Schalthöfer	[GHO00, C96, C03]
Baumweite	Valentin Seiler	Svenja Schalthöfer	[B96, FG06]
Der Satz von Courcelle	Dimitri Rusin	Matthias Hoelzel	[K09, G08]
Cliquenweite	Johannes Rueben	Matthias Hoelzel	[K09, G08]
Lokalität von FO und der Satz von Seese	Jan-Frederik Konopka	Wied Pakusa	[EF95, S95, K09]
FO-Eigenschaften von Strukturen mit lokaler Baumzerlegung	Robert Lipp	Frederic Reinhardt	[FG01]
FO-Eigenschaften von nirgends dichten Graphen (1)	Daniel Steenebrügge	Wied Pakusa	[S16, GKS14]
FO-Eigenschaften von nirgends dichten Graphen (2)	Nikolai von der Burg	Wied Pakusa	[S16, GKS14]
FO-Eigenschaften von nirgends dichten Graphen (3)	Katrin Dannert	Wied Pakusa	[S16, GKS14]
FO-Eigenschaften endlicher abelscher Gruppen entscheiden	Yannic Rohde	Frederic Reinhardt	[Z16]
Mehr zur Komplexität von FO und MSO	Lisa Mannel	Frederic Reinhardt	[FG04]

Literatur

[B96]	H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on computing, vol. 25(6), pp. 1305–1317, 1996.
[C03]	B. Courcelle. The monadic second-order logic of graphs XIV: Uniformly sparse graphs and edge set quantifications. Theoretical Computer Science, vol. 299(1), pp. 1–36, 2003.
[C96]	B. Courcelle. On the Expression of Graph Properties in some Fragments of Monadic Second-Order Logic. Descriptive complexity and finite models, vol. 31, pp. 33–62, 1996.
[EF95]	H. Ebbinghaus and J. Flum. Finite model theory. Springer, 1995.
[FG01]	M. Frick and M. Grohe. Deciding First-order Properties of Locally Tree-decomposable Structures. J. ACM, vol. 48(6), pp. 1184–1206, 2001.
[FG04]	M. Frick and M. Grohe. The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic, vol. 130(1-3), pp. 3–31, 2004.
[FG06]	J. Flum and M. Grohe. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.
[G08]	M. Grohe. Logic, graphs, and algorithms. In Logic and Automata, vol. 2 of Texts in Logic and Games, pp. 357–422. Amsterdam University Press, 2008.
[GHO00]	E. Grädel, C. Hirsch, and M. Otto. Back and Forth Between Guarded and Modal Logics. ACM Transactions on Computational Logics, vol. 3(3), pp. 418 – 463, 2002.
[GK11]	M. Grohe and S. Kreutzer. Methods for algorithmic meta theorems. Model Theoretic Methods in Finite Combinatorics, vol. 558, pp. 181–206, 2011.
[GKS14]	M. Grohe, S. Kreutzer, and S. Siebertz. Deciding first-order properties of nowhere dense graphs. In STOC, pp. 89–98. ACM, 2014.
[K09]	S. Kreutzer. Algorithmic Meta-Theorems. Electronic Colloquium on Computational Complexity (ECCC), vol. 16, pp. 147, 2009.
[S16]	S. Siebertz. Nowhere dense classes of graphs. PhD thesis, 2016.
[S95]	D. Seese. Linear time computable problems and logical descriptions. Electr. Notes Theor. Comput. Sci., vol. 2, pp. 246–259, 1995.
[Z16]	F. A. Zaid. Algorithmic Solutions via Model Theoretic Interpretations. PhD thesis, 2016.

Zuordnung

• 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

Voraussetzungen

• Modul Mathematische Logik
• für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Rückfragen

Erich Grädel, Svenja Schalthöfer, Matthias Hoelzel, Frederic Reinhardt, Wied Pakusa