Vorlesung

Dozent: Volker Diekert

Übungen: die wissenschaftlichen Mitarbeiter der theoretischen Informatik

Ansprechpartner: Armin Weiß

Zeit Raum Termine
Mo 11:30–13:00 0.108 erster Termin: 16.10.2017
Mi 11:30–13:00 0.108  

Der Termin am Mittwoch wird von 9:45 auf 11:30 verlegt.

Inhalt

Bereits 1911 formulierte Max Dehn drei fundamentale algorithmische Probleme in der (kombinatorischen) Gruppentheorie:

  • Wortproblem: Ist ein gegebenes Gruppenelement (als Wort in Erzeugern) das Einselement in der Gruppe?
  • Konjugationsproblem: Sind zwei Elemente konjugiert?
  • Isomorphieproblem: Definieren zwei gegebene Darstellungen isomorphe Gruppen?

Im Allgemeinen sind alle diese Fragen unentscheidbar, also kann man positive Antworten nur in Spezialfällen erhalten. Die weitreichensten Ergebnisse liegen für das Wortproblem vor. Hier gibt es eine große Klasse von Gruppen, die in der Praxis auftreten und für die man sehr gute Algorithmen kennt. In der Vorlesung sollen Techniken behandelt werden, die zu positiven Lösungen zu den obigen Fragen führen und für welche Klasse von Gruppen diese anwendbar sind. Eine prominente Rolle spielen hierbei konfluente Wortersetzungssysteme, die auch in anderen Bereichen zum Einsatz kommen. Insgesamt lebt die Theorie von Querbezügen zu vielen anderen Bereichen, wie Kombinatorik, Topologie, Geometrie, theoretischer Informatik. Dieses Zusammenspiel verschiedener Methoden macht die algorithmische Gruppentheorie sehr attraktiv.

Folien und Skript zur Vorlesung

Übungsblätter

Literatur

  • Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Diskrete algebraische Methoden, Walter de Gruyter, 2013.
  • Lyndon, Schupp: Combinatorial Group Theory, Springer, 1977.

News

[Jun’17] Lukas’ paper “Green’s Relations in Finite Transformation Semigroups” and Armin’s paper “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ both have received a Best Paper Award at the 12th International Computer Science Symposium in Russia (CSR).