..
Suche

Personensuche
Veranstaltungssuche
Katalog der UB Siegen
/ fb12 / ti /
 

Arbeitsgebiete


Prof. Dr. Markus Lohrey

 

In der Forschung beschäftigt sich der Lehrstuhl für Theoretische Informatik mit folgenden Themen:

Algorithmische Modelltheorie

Modelltheorie ist ein klassisches Gebiet der mathematischen Logik, dass sich mit dem Zusammenspiel zwischen den algebraischen und logischen Eigenschaften mathematischer Strukturen beschäftigt. Aus Sicht der Informatik ist jedoch die fehlende algorithmische Ausrichtung der Modelltheorie ein Hindernis. Die algorithmische Modelltheorie versucht, dies zu kompensieren. Im Gegensatz zur klassischen Theorie werden für die Informatik maßgeschneiderte Logiken (z.B. temporale Logiken wie LTL und CTL oder die sehr ausdrucksstarke monadische Logik 2. Stufe) untersucht. Diese Logiken erlauben es, wichtige Systemeigenschaften (z.B. Erreichbarkeit in Graphen) auszudrücken.

Außerdem werden in der algorithmischen Modelltheorie Strukturen untersucht, die mittels abstrakter Maschinenmodelle generiert werden (z.B. Pushdowngraphen und automatische Strukturen). Aktuelle Arbeitsschwerpunkte des Lehrstuhls für Theoretische Informatik bilden die algorithmische Theorie automatischer Strukturen sowie Erweiterungen von Temporallogiken (insbesondere CTL und CTL*) mit Constraints über ganzen Zahlen und anderen Bereichen.

Grammatik-basierte Datenkompression

Datenkompression ist in heutigen informationsverarbeitenden Systemen eine unverzichtbare Komponente. Eine wichtige Klasse von Kompressionsverfahren sind die Wörterbuch-basierten Verfahren, deren Hauptvertreter Varianten der Lempel-Ziv-Kompression sind. Wörterbuch-basierte Kompression ist ein Spezialfall der Grammatik-basierten Kompression. Deren Grundgedanke ist, ein großes Objekt (z.B. ein langer Text oder eine große Baumstruktur) durch eine Grammatik (z.B. eine kontextfreie Wort- oder Baumgrammatik), welche genau das Ausgangsobjekt erzeugt, zu repräsentieren. Im besten Fall ist diese Grammatik exponentiell kleiner als das Ausgangsobjekt. In diesem Kontext beschäftigt sich der Lehrstuhl für Theoretische Informatik hauptsächlich mit der Entwicklung von Algorithmen, welche direkt auf den Grammatiken (also den Komprimaten) anstatt auf den erzeugten Objekten arbeiten. Ein weiterer Arbeitsschwerpunkt ist die Entwicklung leistungsfähiger Grammatik-basierter Baumkompressoren. Ein Hauptanwendungsgebiet für letztere ist die Kompression der aus XML-Dokumenten resultierenden Baumstrukturen.

Algorithmen in der Gruppentheorie

Die Gruppentheorie ist ein Gebiet der Algebra, in dem algorithmische Fragestellungen bereits zu Beginn des 20. Jahrhunderts untersucht wurden. Max Dehn hat in einer bahnbrechenden Arbeit von 1911 drei verschiedene Entscheidungsprobleme für endlich erzeugte Gruppen untersucht: (i) das Wortproblem (Wertet sich ein gegebenes Wort über den Gruppenerzeugern zur Gruppenidentität aus?), (ii) das Konjugationsproblem (Sind zwei durch Wörter über den Gruppenerzeugern gegeben Gruppenelemente konjugiert?) und (iii) das Isomorphieproblem (Sind zwei durch endlich viele definierende Gleichungen gegebene Gruppen isomorph?). Startend mit Arbeiten von Novikov und Boone aus den 1950er Jahren wurden alle drei Probleme als unentscheidbar nachgewiesen. Für viele Klassen von Gruppen sind jedoch Dehns Entscheidungsprobleme sowie Verallgemeinerungen dieser entscheidbar. In diesen Fällen kann nach der Berechnungskomplexität der Probleme gefragt werden. Hier konnten in den letzten Jahren mittels Techniken der Informatik (z.B. Datenkompression, Ersetzungssysteme, Automatentheorie) große Fortschritte erzielt werden. Der Lehrstuhl für Theoretische Informatik wendet beispielsweise Techniken der Grammatik-basierten Kompression zur effizienten Lösung von Wortproblemen an. Des Weiteren untersuchen wir Algorithmen zur Lösung von Gleichungen in Gruppen und rationale Mengen in Gruppen.