Research group Theory of complex systems
News
- Do, 21.8.2014, 15:00, Raum 117: "Expressivity and Succinctness of Order-Invariant Logics on Depth-Bounded Structures" - Vortrag von Frederik Harwath (Goethe-Universität Frankfurt am Main) im TKS-Seminar.
- Papers recently accepted for conferences or workshops:
- Kord Eickmeyer, Michael Elberfeld und Frederik Harwath. Expressivity and Succinctness of Order-Invariant Logics on Depth-Bounded Structures. MFCS 2014.
- André Frochaux, Martin Grohe and Nicole Schweikardt. Monadic Datalog Containment on Trees. AMW 2014.
- Arnaud Durand, Nicole Schweikardt and Luc Segoufin. Enumerating Answers to First-Order Queries over Databases of Low Degree. 2014 ACM SIGMOD/PODS.
- Stephan Kreutzer and Nicole Schweikardt. On Hanf-equivalence and the Number of Embeddings of Small Induced Subgraphs. CSL/LICS 2014.
- Frederik Harwath, Lucas Heimberg and Nicole Schweikardt. Preservation and Decomposition Theorems for Bounded Degree Structures. CSL/LICS 2014.
- Informationen zu den Arbeitsgruppen und angebotenen Modulen im Bereich Grundlagen der Informatik finden Sie hier.
Main Focus
The "Theory of Complex Systems" group focuses on theoretical computer science, with an emphasis on complexity theory, logic, and database theory. Paticular attention is put on the relations between these areas. For example, logics serve as a basis for database query languages and specification languages used for automatic verification; and many aspects of complex systems can be modeled by logical structures, so that properties of complex systems can be specified by logical formulas.
The overall aim of the TKS group is to gain a better understanding of the complexity inherent in a problem or a system. Here, we are interested in various measures of complexity, including the computational complexity (question: How difficult is it to algorithmically solve the problem?) and the descriptive complexity (Question: How difficult is it to describe the problem in a suitable formalism?). Particular attention is paid to the connection between logical descriptions of problems and efficient algorithmic solutions.
One focus of the TKS group is the expressive power and the complexity of various logics. Another focus is the complexity of processing massive data sets and data streams. Here we are particularly interested in designing and analysing computation models suitable for classifying the resources necessary for processing massive data sets and data streams. We aim at developing efficient data stream algorithms as well as proving lower bounds on the costs produced by external memory accesses that are inherently necessary for solving certain problems.