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

  • Blatt 0 (Besprechung am 25.10.)
  • Blatt 1 (Besprechung am 8.11.)
  • Blatt 2 (Besprechung am 22.11. und 6.12.)
  • Blatt 3 (Besprechung am 6.12. und 08.01.)
  • Blatt 4 (Besprechung am 08.01. und 10.01.)
  • Blatt 5 (Besprechung am 05.02.)

Literatur

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

News

[Jan’18] On March 24-29, 2019 Volker Diekert, Markus Lohrey, Olga Kharlampovich and Alexei Miasnikov will organize the Schloss Dagstuhl Seminar “Algorithmic Problems in Group Theory”.

[Dec’17] The paper “The Intersection Problem for Finite Monoids” by Lukas Fleischer and Manfred Kufleitner was accepted at STACS 2018.

[Jun’17] At the 12th International Computer Science Symposium in Russia (CSR), Lukas Fleischer and Manfred Kufleitner received a Best Paper Award for their publication “Green’s Relations in Finite Transformation Semigroups”, and Armin Weiss received a Best Paper Award for “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ which is joint work with Alexei Miasnikov and Svetla Vassileva.