■
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
Automaten über unendlichen Objekten
Datenkompression und Algorithmen
Ergänzungen zu Mathematik II
Formale Sprachen und Automatentheorie
Konkrete Mathematik
■
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
 

Formale Sprachen und Automatentheorie

Vorlesung

Prof. Dr. Ulrich Hertrampf

Termine

Zeit Raum Termine
Di 15:45-17:00 V47.02 wöchentlich ab 08.04.    außer 10.06. bis 01.07.
Do 14:00-15:30 V47.02 wöchentlich ab 10.04.    außer 12.06. bis 26.06.

Erste Vorlesung: 08.04.

Die Scheinliste sowie die Ergebnisse der Scheinklausur hängen neben Raum 1.101 aus. Bitte informieren Sie sich dort vor der Prüfung, ob Sie die Scheinbedingungen erfüllt haben!!

Folien und voraussichtliche Termine:

Vorl. Datum Folien Inhalt
1 08.04. pdf Semesterplanung, Grammatiken: Definitionen und Beispiele
2 10.04. pdf Chomsky-Hierarchie, Wortproblem
3 15.04. pdf Syntaxbäume, Backus-Naur-Form
4 17.04. pdf Reguläre Sprachen: Endliche Automaten, Nichtdet. Automaten (Teil 1)
5 22.04. pdf Nichtdeterministische Automaten (Teil 2)
6 24.04. pdf Reguläre Ausdrücke
7 29.04. pdf Pumping-Lemma und Äquivalenzrelationen
01.05. (Feiertag - Keine Vorlesung)
8 06.05. pdf Minimalautomaten, Erkennung durch Monoide, Abschlusseigenschaften
9 08.05. pdf Entscheidbarkeit, Kontextfreie Sprachen: Normalformen (Teil 1)
10 13.05. pdf Normalformen (Teil 2)
11 15.05. pdf Das Pumping-Lemma (bzw. uvwxy-Theorem) für kontextfreie Sprachen
12 20.05. pdf Abschlusseigenschaften, der CYK-Algorithmus
13 22.05. pdf Kellerautomaten (Teil 1)
14 27.05. pdf Kellerautomaten (Teil 2)
29.05. (Feiertag - keine Vorlesung)
15 03.06. pdf Determin. kontextfreie Sprachen, Entscheidbarkeit bei kontextfr. Sprachen
16 05.06. pdf Kontextsensitive und Typ-0 Sprachen, Turingmaschinen, VU
(keine Vorlesung)
17 03.07. pdf LBA, Satz von Kuroda
08.07. (keine Vorlesung)
18 10.07. pdf Typ 0 und Turingmaschinen, Satz von Immerman und Szelepcsenyi
15.07. SCHEINKLAUSUR
19 17.07. (pdf_alt) Tabellen und Zusammenfassung

Ergänzungen

Martin Seybold, Thomas Mendel

Webseite der Ergänzungen

Übungen

Tobias Walter, Armin Weiß

Informationen zum Übungsbetrieb

Übungsgruppen

Gruppe Tutor Zeit Beginn Raum Besprechung
Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5 Blatt 6
1 Weißer Do 11:30-13:00 24.04. 0.457 24.04. 08.05. 22.05. 05.06. 26.06. 10.07.
2 Wächter Do 11:30-13:00 24.04. 0.463 24.04. 08.05. 22.05. 05.06. 26.06. 10.07.
3 Sauer Do 15:45-17:15 24.04. 0.457 24.04. 08.05. 22.05. 05.06. 26.06. 10.07.
4 Weißer Do 15:45-17:15 24.04. 0.463 24.04. 08.05. 22.05. 05.06. 26.06. 10.07.
5 Walter Fr 8:00-9:30 25.04. 0.463 25.04. 09.05. 23.05. 06.06. 27.06. 11.07.
6 Weiß Fr 14:00-15:30 25.04. 0.124 25.04. 09.05. 23.05. 06.06. 27.06. 11.07.
7 Schnelle Fr 14:00-15:30 25.04. 0.457 25.04. 09.05. 23.05. 06.06. 27.06. 11.07.
8 Bühler Fr 14:00-15:30 25.04. 0.463 25.04. 09.05. 23.05. 06.06. 27.06. 11.07.
9 Schneider Fr 15:45-17:15 25.04. 0.457 25.04. 09.05. 23.05. 06.06. 27.06. 11.07.
10 Bühler Fr 8:00-9:30 25.04. 0.118 25.04. 09.05. 23.05. 06.06. 27.06. 11.07.
11 Walter Fr 8:00-9:30 02.05. 0.463 02.05. 16.05. 30.05. 20.06. 04.07. 18.07.
12 Weiß Fr 14:00-15:30 02.05. 0.124 02.05. 16.05. 30.05. 20.06. 04.07. 18.07.
13 Schnelle Fr 14:00-15:30 02.05. 0.457 02.05. 16.05. 30.05. 20.06. 04.07. 18.07.
14 Bühler Fr 14:00-15:30 02.05. 0.463 02.05. 16.05. 30.05. 20.06. 04.07. 18.07.
15 Schneider Fr 15:45-17:15 02.05. 0.457 02.05. 16.05. 30.05. 20.06. 04.07. 18.07.
16 Bühler Fr 8:00-9:30 02.05. 0.118 02.05. 16.05. 30.05. 20.06. 04.07. 18.07.
17 Reingruber Di 17:30-19:00 22.04. 0.124 22.04. & 29.04. 06.05. & 13.05. 20.05. & 27.05. 03.06. & 17.06. 24.06. & 01.07. 08.07. & 15.07.
18 Reingruber Mi 17:30-19:00 23.04. 0.124 23.04. & 30.04. 07.05. & 14.05. 21.05. & 28.05. 04.06. & 18.06. 25.06. & 02.07. 09.07. & 16.07.

Übungsblätter

Literatur

  • Uwe Schöning: Theoretische Informatik – kurzgefasst, 5. Auflage, Spektrum, 2008. (Die ältere Auflage von 2000 tut’s auch!)
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison-Wesley, 2002.

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.