■
Team
■
Teaching
Oberseminar der Theorie
■
Winter 2023
■
Summer 2023
■
Winter 2022
■
Summer 2022
■
Winter 2021
■
Summer 2021
■
Winter 2020
■
Summer 2020
■
Winter 2019
■
Summer 2019
■
Winter 2018
■
Summer 2018
■
Winter 2017
■
Summer 2017
■
Winter 2016
■
Summer 2016
■
Winter 2015
■
Summer 2015
■
Winter 2014
■
Summer 2014
■
Winter 2013
■
Summer 2013
■
Winter 2012
■
Summer 2012
■
Winter 2011
Former Semester
BSc, Master-, Student-, Diplomathesis
StuPro/ ProjektINF/ SoPra/ FaPra
Exam Archive
Standard Textbooks
Descriptive Theory
■
Research
■
Publications
 

Oberseminar der Theorie

Prof. Dr. Volker Diekert, Prof. Dr. Ulrich Hertrampf

Inhalte der Veranstaltung

Im Oberseminar werden aktuelle Arbeiten aus dem Bereich der Theoretischen Informatik vorgetragen, meist von Diplomand(inn)en und Mitarbeiter(innen), aber auch von auswärtigen Gästen. Theorie-Interessierte sind jederzeit willkommen.

Zeit Raum
Dienstag 14:00 – 15:30 Uhr 0.108

Voraussichtliche Planung

TBA

Vorträge der letzten Semester (bis 2019)

Termin Vortragender Thema
06.02.2019 Jan Philipp Wächter Inverse and Partial Automaton Semigroups
30.01.2019 Ulrich Hertrampf Entscheidbarkeitsresultate zur Theorie der Wörter mit der Infix-Ordnung, Teil 2
23.01.2019 Ulrich Hertrampf Entscheidbarkeitsresultate zur Theorie der Wörter mit der Infix-Ordnung
16.01.2019 Florian Barth Multikriterielle Alternativeroutenplanung
19.12.2018 Volker Diekert Paritätsspiele in Quasipolynomieller Zeit
12.12.2018 Florian Stober Average Case Considerations for MergeInsertion
05.12.2018 Lukas Fleischer Cayley Semigroup Membership für Varietäten endlicher Monoide (Teil 2)
28.11.2018 Jan Philipp Wächter Semidirekte Produkte der freien monogenischen Halbgruppe sind keine Automatenhalbgruppen
07.11.2018 Lukas Fleischer Cayley Semigroup Membership für Varietäten endlicher Monoide
11.07.2018 Carlos Camino Merge decompositions, two-sided Krohn-Rhodes, and aperiodic pointlikes
06.07.2018 Volker Diekert Merge decompositions, two-sided Krohn-Rhodes, and aperiodic pointlikes
04.07.2018 Volker Diekert Beweis des zweiseitigen Krohn-Rhodes Satzes nach van Gool und Steinberg: Merge decompositions, two-sided Krohn-Rhodes, and aperiodic pointlikes
27.06.2018 Volker Diekert Einführung in die Theorie endlicher Halbgruppen und Pointlike-Sets, Teil 2
20.06.2018 Volker Diekert Einführung in die Theorie endlicher Halbgruppen und Pointlike-Sets
13.06.2018 Jan Philipp Wächter Orbits in Automatenhalbgruppen, Teil 3
06.06.2018 Ulrich Hertrampf Wenn Schlümpfe Pizza teilen
30.05.2018 Jan Philipp Wächter Orbits in Automatenhalbgruppen, Teil 2
15.05.2018 Jan Philipp Wächter Orbits in Automatenhalbgruppen
09.05.2018 Lukas Fleischer Graham’s Theorem and the Membership Problem for EA
02.05.2018 Johannes Schäufele et al. Parallel BlockQuicksort
25.04.2018 Lukas Fleischer FO-definierbare Pseudovarietäten endlicher Halbgruppen
19.04.2018 Volker Diekert Wortgleichungen über SL(2,Z)
13.04.2018 Jarkko Heidenwag Durchschnittsanalyse für Quicksort mit Links-Rechts-Partitionierung im Fall vieler Duplikate
07.02.2018 Armin Weiß Minimum cuts and structure trees of context free groups, Part 7: Guessing graph of groups
31.01.2018 Lukas Fleischer Die Komplexität des “Cayley Semigroup Membership”-Problems
24.01.2018 Armin Weiß Minimum cuts and structure trees of context free groups, Part 6: Computing nested cuts
20.12.2017 Armin Weiß Minimum cuts and structure trees of context free groups, Part 5: Computing the graph of groups
13.12.2017 Géraud Sénizergues Minimum cuts and structure trees of context free groups, Part 4: Computing optimal cuts
06.12.2017 Armin Weiß Minimum cuts and structure trees of context free groups, Part 3: Tilings
29.11.2017 Armin Weiß Minimum cuts and structure trees of context free groups, Part 2
22.11.2017 Besik Dundua Solving Hedge Regular and Context Regular Inequalities
15.11.2017 Armin Weiß Minimum cuts and structure trees of context free groups
08.11.2017 Lukas Fleischer The Complexity of the Intersection Problem for Finite Monoids, Teil 2
25.10.2017 Steffen Bußmann et al. AMX - A Toolkit for Automata and Monoids
25.10.2017 Lukas Fleischer The Complexity of the Intersection Problem for Finite Monoids
01.09.2017 Volker Diekert Ein Theorem von Schützenberger: a finite maximal code having finite deciphering delay is prefix
19.07.2017 Lukas Fleischer Unär kodierte PSPACE-vollständige Sprachen in ASPACE(log log n)
05.07.2017 Besik Dundua An Overview of PρLog
21.07.2017 Volker Diekert Twisted Word Equations
31.05.2017 Tomas Masopust Partially Ordered Nondeterministic Finite Automata
31.05.2017 Jan Philip Wächter Über das Freiheitsproblem von Automatenhalbgruppen und -gruppen
24.05.2017 Manfred Kufleitner Locally threshold testable languages, Teil 2
10.05.2017 Manfred Kufleitner Locally threshold testable languages
03.05.2017 Manfred Kufleitner Locally testable languages
26.04.2017 Armin Weiß Einführung in Nilpotente Gruppen, Teil 2
19.04.2017 Armin Weiß Einführung in Nilpotente Gruppen
05.04.2017 Artur Jez Word equations in nondeterministic linear space
08.02.2017 Ralf Küsters Informationssicherheit
23.11.2016 Volker Diekert Einführung in Chaitins Zahl Omega und in die generische Komplexitätstheorie
16.11.2016 Jonathan Kausch Lexikographische topologische Sortierungen
09.11.2016 Tobias Walter Das Abtast-Theorem
02.11.2016 Jan Philipp Wächter Titel: Über das freie Produkt von Automatenhalbgruppen
26.10.2016 Lukas Fleischer Die R-Höhe in endlichen Transformations-Monoiden
06.07.2016 Tobias Walter Characterising classes of regular languages using prefix codes of bounded synchronisation delay
29.06.2016 Jan Phillip Wächter Die Grigortschuk-Gruppe, Teil 3
22.06.2016 Ulrich Hertrampf Zusammenhänge aus der strukturellen Komplexitätstheorie, Teil 2
15.06.2016 Ulrich Hertrampf Zusammenhänge aus der strukturellen Komplexitätstheorie
08.06.2016 Jan Phillip Wächter Die Grigortschuk-Gruppe, Teil 2
01.06.2016 Jan Phillip Wächter Die Grigortschuk-Gruppe
25.05.2016 Jonathan Kausch Reduzieren und Berechnen einer Normalform in Graph-Produkten, Teil 2
11.05.2016 Jonathan Kausch Reduzieren und Berechnen einer Normalform in Graph-Produkten
27.04.2016 Jan Philip Wächter Automaten-(Halb-)Gruppen, Teil 3
20.04.2016 Jan Philip Wächter Automaten-(Halb-)Gruppen, Teil 2
13.04.2016 Jan Philip Wächter Automaten-(Halb-)Gruppen

News

[Jun’23] The paper “Parallel algorithms for power circuits and the word problem of the Baumslag group” by Caroline Mattes and Armin Weiß has been accepted at Computational Complexity.

[Oct’22] The paper “Lower Bounds for Sorting 16, 17, and 18 Elements” by Florian Stober and Armin Weiß has been accepted at ALENEX 2023.

[Sep’22] The paper “Conelikes and Ranker Comparisons” by Viktor Henriksson and Manfred Kufleitner has been accepted at LATIN 2022.

[Sep’22] The paper “Improved Parallel Algorithms for Generalized Baumslag Groups” by Caroline Mattes and Armin Weiß has been accepted at LATIN 2022.

[Apr’22] The paper “Reachability Games and Parity Games” by Volker Diekert and Manfred Kufleitner has been accepted at ICTAC 2022.

[Apr’22] The paper “Satisfiability Problems for Finite Groups” by Pawel M. Idziak, Piotr Kawalek, Jacek Krzaczkowski and Armin Weiß has been accepted at ICALP 2022.

[Mar’22] The paper “The Power Word Problem in Graph Products” by Florian Stober and Armin Weiß was accepted at DLT 2022.

[Nov’20] Volker Diekert is Partner Investigator in the Australian ARC grant “Geodetic groups: foundational problems in algebra and computer science” at University of Technology Sydney.

[Apr’20] The paper “Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems” by Laurent Bartholdi, Michael Figelius, Markus Lohrey and Armin Weiß has been accepted at CCC 2020.

[Apr’20] The paper “Hardness of equations over finite solvable groups under the exponential time hypothesis” by Armin Weiß has been accepted at ICALP 2020.

[Dec’19] The paper “An Automaton Group with PSPACE-Complete Word Problem” by Jan Philipp Wächter and Armin Weiß has been accepted at STACS 2020.

[Nov’19] Carlos Camino was awarded the stuvus Special Prize for exceptional commitment in teaching.

[Jun’19] The paper “The power word problem” by Markus Lohrey and Armin Weiß has been accepted at MFCS 2019.

[May’19] The paper “On the Average Case of MergeInsertion” by Florian Stober and Armin Weiß has been accepted at IWOCA 2019.

[Oct’18] The paper “Worst-Case Efficient Sorting with QuickMergesort” by Stefan Edelkamp and Armin Weiß has been accepted at ALENEX 2019.

[Jun’18] At CCC 2018, Lukas Fleischer received a Best Student Paper Award for his submission “On the Complexity of the Cayley Semigroup Membership Problem”.

[Jun’18] The paper “Testing Simon’s congruence” by Lukas Fleischer and Manfred Kufleitner was accepted at MFCS 2018.

[Jun’18] The paper “The Intersection Problem for Finite Semigroups” by Lukas Fleischer was accepted at DLT 2018.

[Apr’18] The paper “The isomorphism problem for finite extensions of free groups is in PSPACE” by Géraud Sénizergues and Armin Weiß was accepted at ICALP 2018.

[Apr’18] The paper “On the Complexity of the Cayley Semigroup Membership Problem” by Lukas Fleischer was accepted at CCC 2018.

[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.