■
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
 

Automaten über unendlichen Objekten

Organisatorisches

Dozenten:
Manfred Kufleitner (Raum 1.160, Tel. 0711 / 685 88231)
Volker Diekert (Raum 1.125, Tel. 0711 / 685 88329)

Vorlesungstermine:

Zeit Raum Termine Vorlesung
Mo 11:30–13:00 0.108 wöchentlich
Fr 11:30–13:00 0.108 vierzehntäglich im Wechsel mit der Übung

Bitte beachten Sie kurzfristige Termin- und Raumänderungen, die an dieser Stelle veröffentlicht werden.

Übungstermine:

Zeit Raum Termine Übungen
Fr 11:30–13:00 0.108 vierzehntäglich mit der Vorlesung im Wechsel

Die Übungen am 23.05. finden um 14:00 Uhr im Raum 0.363 statt.

Vorlesungsmitschrieb

  • 07.04.2014: Presburger Arithmetik [PDF1] [PDF2] [PDF3]
  • 11.04.2014: unendliche Wörter, Büchi-Automaten, deterministische Büchi-Automaten, Vereinigung und Durchschnitt [PDF1] [PDF2] [PDF3] [PDF4] [PDF5]
  • 14.04.2014: omega-rationale Sprachen, der Satz von Ramsey, Erkennbarkeit, syntaktische Kongruenz nach Arnold [PDF1] [PDF2] [PDF3] [PDF4] [PDF5] [PDF6] [PDF7]
  • 25.04.2014: Komplementabschluss und syntaktische Monoide [PDF1] [PDF2] [PDF3] [PDF4]
  • 28.04.2014: keine Vorlesung
  • 02.05.2014: Äquivalente Charakterisierungen der Erkennbarkeit, Entscheidungsprobleme für Büchi-Automaten [PDF1] [PDF2] [PDF3] [PDF4] [PDF5] [PDF6] [PDF7]
  • 05.05.2014: MSO-Logik: von Automaten zu Formeln [PDF]
  • 09.05.2014: MSO-Logik: von Formeln zu Automaten, andere Automatenmodelle für omega-reguläre Sprachen [PDF1] [PDF2]
  • 12.05.2014: weitere Automatenmodelle, Umwandlungen zwischen den Automatenmodellen, Safra-Konstruktion (Teil 1) [PDF1] [PDF2] [PDF3] [PDF4]
  • 16.05.2014: Safra-Konstruktion (Teil 2), von deterministischen Muller-Automaten zu deterministischen Rabin-Automaten (Teil 1) [PDF1] [PDF1-Nachtrag] [PDF2] [[PDF3]][20140516c]
  • 19.05.2014: von deterministischen Muller-Automaten zu deterministischen Rabin-Automaten und zu deterministische Parity-Automaten (Teil 2), untere Schranke für Büchi-Komplementierung nach Max Michel, von Streett-Automaten zu Büchi-Automaten, untere Schranke für Safra-Konstruktion [PDF1] [PDF2] [PDF3]
  • 23.05.2014: Klarlunds Konstruktion (Teil 1), Ordinalzahlen, Berechnungsgraph [PDF1] [PDF2] [PDF3] [PDF4]
  • 26.05.2014: Klarlunds Konstruktion (Teil 2), Korrektheit von Klarlunds Konstruktion ohne Auswahlaxiom [PDF1] [PDF2]
  • 30.05.2014: Pfeilsprachen, omega-reguläre Sprachen sind Boolesche Kombinationen von deterministischen Sprachen, weak-MSO-Logik, der Satz von Landweber über deterministische Sprachen [PDF1] [PDF2]
  • 02.06.2014: Cantor-Topologie, deterministische Sprachen und Borel-Hierarchie, offene omega-reguläre Sprachen [PDF1] [PDF2] [PDF3]
  • 06.06.2014: keine Vorlesung
  • 16.06.2014: Schwache Akzeptanzbedingungen [PDF]
  • 20.06.2014: Staiger-Wagner-Automaten, Carton-Michel-Automaten (Teil 1) [PDF1] [PDF2] [PDF3] [PDF4] [PDF5]
  • 23.06.2014: Carton-Michel-Automaten (Teil 2) [PDF1] [PDF2]
  • 27.06.2014: Topologischer Abschluss, Kompaktheit der Cantor-Topologie [PDF]
  • 30.06.2014: Monitorability [PDF]
  • 04.07.2014: Linear Temporal Logic (LTL): Syntax und Semantik [PDF]
  • 07.07.2014: Aperiodische Monoide, lokale Divisoren, von aperiodisch zu LTL (Teil 1) [PDF1] [PDF2] [PDF3]
  • 11.07.2014: Von aperiodisch zu LTL (Teil 2) [PDF]
  • 14.07.2014: Von LTL zu FO3, von FO zu sternfrei, von sternfrei zu aperiodisch [PDF1] [PDF2] [PDF3] [PDF4] [PDF5]

Übungsblätter

  • Blatt 1 (PDF, Besprechung am 25.04. um 14:00 Uhr im Raum 0.363)
  • Blatt 2 (PDF, Besprechung am 9.05. um 14:45 Uhr im Raum 0.363)
  • Blatt 3 (PDF, Besprechung am 23.05. um 14:00 Uhr im Raum 0.363)
  • Ideen für kleine Forschungsprojekte
  • Wir treffen uns am 18.07.2014 um 11:30 Uhr im Raum 0.108.

Materialien

  • Skript zur Vorlesung Automaten über unendlichen Wörtern vom Wintersemester 2011/2012 [PDF]

Literatur

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.