■
Team
■
Teaching
Oberseminar der Theorie
■
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
Mittwoch 11:30 – 13:00 Uhr 0.108

Voraussichtliche Planung

Termin Vortragender Thema
07.11.2018 Lukas Fleischer Cayley Semigroup Membership für Varietäten endlicher Monoide
14.11.2018   Kein Oberseminar
21.11.2018 Volker Diekert Equations in Free Inverse Monoids (Folien)
28.11.2018 Jan Philipp Wächter  
05.12.2018 Jan Philipp Wächter  
12.12.2018    
19.12.2018 Armin Weiß  

Vorträge der letzten Semester

Termin Vortragender Thema
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

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