Groups in the Institute for Theoretical Computer Science

The algorithms group focuses on the development of algorithmic methods and on exploring their inherent limitations.

The two key questions are:

  • In which situations do efficient algorithms exist and what is the structural difference between "easy" and "hard" input instances?
  • What are the strengths and limits of certain algorithmic strategies and solution methods?

The investigated settings include classic decision problems (such as the satisfiability test of propositional logic), counting and enumeration algorithms (determining the number of or generate all solutions) to dynamic algorithms that support efficient update operations.

Concrete fields of application of this research are

  • methods for query optimization and query evaluation on relational and probabilistic databases as well as
  • methods and data structures in the area of ​​SAT and constraint solving.

The research interests of the Automata and Logic group are in the areas of methods for automatic verification of distributed systems and automatic structures. In particular, these investigations use methods from logic and automata theory, and thus belong to the broader area of logic in computer science.

In automatic verification, we try to find a trade-off between the expressiveness of specification languages and their algorithmic controllability. In this context, recently gained theoretical insights on distributed models with finitely many internal states are also investigated, adapted and extended with respect to their practical relevance.

In addition to these systems, the verification of those with infinitely many internal states (which can occur, for example, due to stacks or string variables) is also of interest. An abstract model of these systems are automatic structures. We study these structures from the algorithmic side (Which questions are solvable with which effort?) and from the abstract side (Which model-theoretic properties characterize these structures?).