Research areas at the chair of Theoretical Computer Science
Our research is centered around the following topics:
Grammar-based compression
Due to the huge amount of data in modern information processing systems, data compression became a key technology in computer science. An important class of compressors are dictionary-based compressors. Famous examples are the Lempel-Ziv compression algorithms. Another class of dictionary-based compressors that received a lot of attention in the past 10 years are grammar-based compressors. The basic idea is to compress a large object (e.g. a text or a large tree structure) by a grammar (e.g. a context-free string or tree grammar) that only produces the initial object. In the best case, this grammar can be exponentially smaller than the initial object.
In many applications, compressed data have to be processed. A typical example is the search for specific patterns in compressed genome data bases. In these applications it is often not feasible to first decompress the data and then process it. We are working on algorithms which directly compute on the grammar instead of decompressing the grammar first. Another research project are techniques for deriving precise quantitative statements on the compression ratio of grammar-based string and tree compressors.
Algorithms in group theory
Group theory is a part of algebra, where algorithmic problems have been studied since the beginning of the 20th century. Max Dehn defined in his seminal paper from 1911 three decision problems for finitely generated infinite groups: (i) the word problem (does a given word over the group generators evaluate to the group identity?), (ii) the conjugacy problem (do two given words over the group generators represent conjugated group elements?), and (iii)the isomorphism problem (are two finitely presented groups that are given by defining relations isomorphic?) Starting with the work of Novikov and Boone from the 1950's, all three problems turned out to be undecidable in general. On the other hand, for many special classes of groups, Dehn's decision problems and generalizations of these are decidable. In these cases one can ask for the computational complexity of the problems. In recent years, considerable process has been made in this direction by using techniques from computer science (e.g. data compression, rewriting systems, automata theory). In our group, we use for instance techniques from grammar-based compression in order to develop more efficient algorithms for the solution of word problems. Moreover, we look at algorithms for the solution of equations in groups and rational sets in groups.
Streaming algorithms
Streaming algorithms are algorithms that do not get random access on the input data. Instead, the algorithm receives one new symbol/data value at each time instant. Streaming algorithms are important in big data analytics, where random access on the whole input is not feasible. In recent years we developed an automata theoretic approach to streaming algorithms. Our focus was on deterministic and randomized sliding window streaming algorithms for formal languages (in particular, regular languages and context-free languages), where only the last n data items are relevant at each time instant (n is the window size).
Algorithmic Model Theory
Model theory is a classical area in mathematical logic, which studies the interplay between the algebraic and logical properties of structures. For applications in computer science, this missing algorithmic focus in model theory is an obstacle. Algorithmic model theory compensates this. Its focus is on structures that are defined by abstract machine models, like finite automata or pushdown machines. Whereas classical model theory is mainly concerned with first-order logic, algorithmic model theory also studies logics that are tailored towards applications in areas like automatic verification or database theory. Examples for such a logics are temporal logics like LTL and CTL, or the highly expressive monadic second order logic. These logics can expressive important system properties like reachability or fairness.
Current research topics at the chair for Theoretical Computer Science include the algorithmic theory of automatic structures and temporal logics with numerical constraints.