Unsere Arbeit

Die Arbeiten dieser Forschungsgruppe befassen sich mit algorithmischen Problemen in algebraischen und kombinatorischen Systemen. Um in mathematischen Strukturen effektiv rechnen zu können, müssen diese Strukturen durch eine endliche Beschreibung dargestellt werden. Damit hat man es bei der Behandlung dieser Strukturen im Wesentlichen nicht mit den Strukturen selbst, sondern nur mit ihren Darstellungen zu tun. Dies führt sofort zu einer Reihe grundlegender algorithmischer Probleme, deren Einfachstes das Wort- oder Äquivalenzproblem ist: Entscheide, ob zwei Darstellungen dieselbe Struktur beschreiben!

Reduktions- oder Ersetzungstechniken haben sich als sehr nützlich für das Lösen zahlreicher algorithmischer Probleme in algebraischen und kombinatorischen Systemen erwiesen. Allgemeine Ersetzungssysteme wie Termersetzungssysteme und Graphgrammatiken haben Anwendungen bei der Behandlung abstrakter Datentypen, bei der Formelmanipulation, bei der automatischen Programmtransformation, beim automatischen Beweisen und in der Computeralgebra gefunden.

Daher interessiert man sich für die Möglichkeiten und die Grenzen dieser Reduktions- oder Ersetzungstechniken. Dies ist der Schwerpunkt der Arbeiten dieser Gruppe.

Ein weiterer Schwerpunkt liegt auf dem klassischen Gebiet der Automatentheorie und der Formalen Sprachen. Insbesondere interessiert dabei natürlich die Wechselwirkung zwischen diesem Gebiet und dem der Reduktionstechniken.