Research interests

From a mathematical point of view the computability theory deals with the idea of the calculation, or the algorithm. Different models for composing the idea of the calculation are considered and their possibilities are explored. The computability theory is closely related to the mathematical logic.

In Circuit Complexity, circuits are considered as calculation models. This results in different measures for the resource requirement than in classical complexity theory. We are particularly interested in the connection of certain circuit classes, first-level logic classes and algebra. [read more ...]

In addition to the question of how a problem can be solved algorithmically, the question of the efficiency of such an algorithmic solution is a fundamental component of computer science. The theory of complexity deals with the question of the required resources to solve a problem. [read more ...]

Fixed-parameter algorithms provide optimal solutions to given discrete combinatorial problems. As a rule, the problems considered are NP-difficult, so you have to deal with exponential run-time. However, the exponential growth of the runtime may only depend on certain, problem-specific parameters that are part of the input. The goal is to identify such parameters: if the values ​​of these parameters are then small in concrete applications of the particular problem, the exponential growth may be accepted and the problem can be solved efficiently with a fixed-parameter algorithm. Such a parameter can be, for example, the top of a graph: many graph problems are quickly solvable for graphs with a small tree.

Parametrized algorithms provide exact solutions, making them an interesting alternative to heuristics and approximative algorithms.

Formal languages are an essential instrument of the theoretical computer science to formalise problem statements. They enable a structured and linearized representation of data. Applications in practice can be found, for example, in compiler construction. Known examples of formal languages that occur in practice are programming languages or HTML and XML. [read more ...]