News

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.

Deadlines

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

Schedule

Montag, 23. Januar
10:00	–	10:30	Marko van Treeck	Fixed-parameter tractability
10:35	–	11:05	Oliver Feith	Hierarchies in parameterised complexity theory
11:10	–	11:40	Lukas Rodenbüsch	Variants of monadic second order logic
13:00	–	13:30	Valentin Seiler	Tree width
13:35	–	14:05	Dimitri Rusin	Courcelle's Theorem
14:10	–	14:40	Johannes Rueben	Clique width
14:45	–	15:15	Jan-Frederik Konopka	Locality of first-order logic and Seese's Theorem
Dienstag, 24. Januar
11:00	–	11:30	Robert Lipp	FO properties of locally tree-decomposable structures
13:00	–	13:30	Daniel Steenebrügge	FO properties of nowhere dense graphs (1)
13:35	–	14:05	Nikolai von der Burg	FO properties of nowhere dense graphs (2)
14:10	–	14:40	Katrin Dannert	FO properties of nowhere dense graphs (3)
14:45	–	15:15	Yannic Rohde	Deciding FO properties of finite Abelian groups

Topics

Thema	Vortragende(r)	Betreuer(in)	Literatur
Fixed-parameter tractability	Marko van Treeck	Matthias Hoelzel	[FG06]
Hierarchies in parameterised complexity theory	Oliver Feith	Svenja Schalthöfer	[FG06]
Variants of monadic second order logic	Lukas Rodenbüsch	Svenja Schalthöfer	[GHO00, C96, C03]
Tree width	Valentin Seiler	Svenja Schalthöfer	[B96, FG06]
Courcelle's Theorem	Dimitri Rusin	Matthias Hoelzel	[K09, G08]
Clique width	Johannes Rueben	Matthias Hoelzel	[K09, G08]
Locality of first-order logic and Seese's Theorem	Jan-Frederik Konopka	Wied Pakusa	[EF95, S95, K09]
FO properties of locally tree-decomposable structures	Robert Lipp	Frederic Reinhardt	[FG01]
FO properties of nowhere dense graphs (1)	Daniel Steenebrügge	Wied Pakusa	[S16, GKS14]
FO properties of nowhere dense graphs (2)	Nikolai von der Burg	Wied Pakusa	[S16, GKS14]
FO properties of nowhere dense graphs (3)	Katrin Dannert	Wied Pakusa	[S16, GKS14]
Deciding FO properties of finite Abelian groups	Yannic Rohde	Frederic Reinhardt	[Z16]
The complexity of FO and MSO revisited	Lisa Mannel	Frederic Reinhardt	[FG04]

Literature

[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.

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, Svenja Schalthöfer, Matthias Hoelzel, Frederic Reinhardt, Wied Pakusa