Univ.-Prof. Dr. Markus Lohrey

1991-1996: Studium der Informatik an der Friedrich-Alexander Universität Erlangen-Nürnberg

1999: Promotion (Dr. rer. nat.) in Informatik an der Universität Stuttgart

2003: Habilitation in Informatik an der Universität Stuttgart

2007-2013: Professor (W2) für algebraische und logische Grundlagen der Informatik an der Universität Leipzig

seit 2013: Professor (W3) für theoretische Informatik an der Universität Siegen

Aufgrund der enorm wachsenden Datenmengen (Stichwort Big Data) in der heutigen Zeit ist die Datenkompression zu einer Schlüsseltechnologie der Informatik geworden. Eine wichtige Klasse von Kompressoren sind die wörterbuchbasierten Kompressoren. Berühmte Beispiele sind die Lempel-Ziv-Kompressionsalgorithmen. Eine andere Klasse wörterbuchbasierter Kompressoren, die in den letzten zehn Jahren viel Aufmerksamkeit erhalten hat, sind grammatikbasierte Kompressoren. Die Grundidee besteht darin, ein großes Objekt (z. B. einen Text oder eine große Baumstruktur) durch eine Grammatik (z. B. eine kontextfreie String- oder Baumgrammatik) zu komprimieren, die genau dieses Objekt erzeugt. Im besten Fall kann diese Grammatik exponentiell kleiner sein als das ursprüngliche Objekt.

In vielen Anwendungen müssen komprimierte Daten weiterverarbeitet werden. Ein typisches Beispiel ist die Suche nach bestimmten Mustern in komprimierten Genomdatenbanken. In solchen Anwendungen ist es oft nicht praktikabel, die Daten zuerst zu dekomprimieren und sie dann zu verarbeiten. Wir arbeiten an Algorithmen, die direkt auf der Grammatik operieren, anstatt sie vorher zu dekomprimieren. Ein weiteres Forschungsprojekt befasst sich mit Techniken zur präzisen quantitativen Abschätzung des Kompressionsverhältnisses von grammatikbasierten String- und Baumkompressoren.

Die Gruppentheorie ist ein Teilgebiet der Algebra, in dem algorithmische Probleme bereits seit Beginn des 20. Jahrhunderts untersucht werden. Max Dehn formulierte in seiner bahnbrechenden Arbeit von 1911 drei Entscheidungsprobleme für endlich erzeugte unendliche Gruppen:
(i) das Wortproblem (wertet ein gegebenes Wort über den Gruppen-Erzeugern zur Gruppeneinheit aus?),
(ii) das Konjugationsproblem (repräsentieren zwei gegebene Wörter über den Gruppen-Erzeugern konjugierte Gruppenelemente?), und
(iii) das Isomorphieproblem (sind zwei endlich präsentierte Gruppen, die durch Relationen definiert sind, isomorph?).

Seit den Arbeiten von Novikov und Boone aus den 1950er Jahren weiß man, dass alle drei Probleme im Allgemeinen unentscheidbar sind. Andererseits sind Dehns Entscheidungsprobleme und deren Verallgemeinerungen für viele spezielle Klassen von Gruppen entscheidbar. In diesen Fällen stellt sich die Frage nach der berechnungstheoretischen Komplexität dieser Probleme. In den letzten Jahren wurden auf diesem Gebiet erhebliche Fortschritte erzielt, insbesondere durch den Einsatz von Techniken aus der Informatik (z. B. Datenkompression, Ersetzungssysteme, Automatentheorie). In unserer Arbeitsgruppe verwenden wir beispielsweise Methoden der grammatikbasierten Kompression, um effizientere Algorithmen zur Lösung von Wortproblemen zu entwickeln. Darüber hinaus untersuchen wir Algorithmen zur Lösung von Gleichungen in Gruppen sowie für rationale Mengen in Gruppen.

Streaming-Algorithmen sind Algorithmen, die keinen wahlfreien Zugriff auf die Eingabedaten haben. Stattdessen erhält der Algorithmus zu jedem Zeitpunkt ein neues Symbol bzw. einen neuen Datenwert. Streaming-Algorithmen sind besonders wichtig in der Big-Data-Analyse, wo ein direkter Zugriff auf die gesamten Eingabedaten nicht möglich ist. In den letzten Jahren haben wir einen automatentheoretischen Ansatz für Streaming-Algorithmen entwickelt. Ein Fokus unserer Forschung liegt auf deterministischen und randomisierten Sliding-Window-Streaming-Algorithmen für formale Sprachen (insbesondere reguläre und kontextfreie Sprachen), bei denen zu jedem Zeitpunkt nur die letzten n Datenelemente relevant sind (n ist die Fenstergröße). In jüngster Zeit haben wir auch Streaming-Algorithmen für Probleme aus der algorithmischen Gruppentheorie untersucht. 

Das zentrale algorithmische Problem der Datenbanktheorie ist die Berechnung aller Lösungen (query results) für eine Datenbankanfrage (query). Letztere ist typischerweise in einem Fragment einer Logik (wie z.B. Logik 1. Stufe oder monadische Logik 2. Stufe) formuliert. Häufig ist die Größe der Lösungsmenge exponentiell in der Eingabelänge, was die gesamte Berechnung der Lösungsmenge inhärent schwer macht. In solchen Fällen bieten Aufzählungsalgorithmen (enumeration algorithms) eine realistischere Perspektive. Die Rechenzeit eines Aufzählungsalgorithmus wird typischerweise gemessen durch (i) die Zeit für die Vorverarbeitung der Daten und (ii) die maximale Zeit, die zwischen der Ausgabe von zwei Lösungen vergeht (Verzögerung). Den Goldstandard setzen Aufzählungsalgorithmen, wo die Vorverarbeitung linearer Zeit benötigt, und die Verzögerung für jede neue generierte Lösung linear in der Länge dieser Lösung ist (output linear delay). Wir beschäftigen uns mit Aufzählungsalgorithmen für Datenbankanfragen, wo die Daten komprimiert (z.B. in Form einer Grammatik) vorliegen.