Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

Vorlesung Automatentheorie

 


 


Aktuelles

 

  • Leider findet am 11. Juni 2024 keine Vorlesung statt.
  • 14. Mai 2024: Krankheitsbedingt muss die Vorlesung heute leider entfallen.
  • 30. April 2024: Krankheitsbedingt muss die Vorlesung heute leider entfallen.
  • Vorerst haben wir vereinbart:  Die Vorlesung fängt dienstags Punkt 15:00 Uhr und freitags Punkt 11:00 Uhr an. Nach einem entspannten Mittagessen treffen wir uns dann freitags 13:30 Uhr zur Übung.
  • Die Eröffnungsvorlesung fand am Freitag, dem 19. April 2024, statt.

 


Einführung

 

Wir befassen uns in der Vorlesung mit der Theorie endlicher Automaten auf endlichen und unendlichen Wörtern, sowie auf Bäumen. Hierbei untersuchen wir verschiedene Typen von Automaten, deren Abschlusseigenschaften und Umwandlungsmöglichkeiten zwischen verschiedenen Modellen, verschiedene Entscheidungsprobleme (bspw. Leerheits- oder das Äquivalenzproblem) und deren Beziehungen zu verschiedenen Logiken wie LTL, CTL und MSO.

 


Logbuch

 

Im Logbuch werden regelmäßig Informationen bekannt gegeben.

 


Termine

 

Vorlesung
Dienstag 15:00-17:00, Schrödinger-Zentrum (RUD26), Raum 1'305 und
Freitag    11:00-13:00, Schrödinger-Zentrum (RUD26), Raum 1'305
Übung
Freitag    13:00-15:00, Schrödinger-Zentrum(RUD26),Raum1'305

Tutor:   

Dorian Gutschenreiter

 

 


Übungsblätter

 

Ab der zweiten Vorlesungswoche wird wöchentlich, jeweils freitags  ein Übungsblatt hier und im Moodle-Kurs online bereitgestellt.

 

Verbindliche "Spielregeln" zum Erwerb von Übungspunkten

Sie können bei jedem Übungsblatt entscheiden, gemäß welcher der folgenden beiden Varianten A bzw. B Ihre Lösung bewertet werden soll:

Variante A:
Sie geben eine schriftliche, ausführlich ausgearbeitete und mathematisch präzise Lösung spätestens direkt vor Beginn der Übungsstunde am Freitag im Moodle-Kurs ab.

Variante B:
Sie geben keine Lösung ab. Stattdessen tragen Sie direkt vor Beginn der Übung in eine bereitgestellte Liste ein, wie viele Übungspunkte Sie für Ihre Lösung der einzelnen Aufgaben(teile) für gerechtfertigt halten. Während der Übungsstunde werden aus dieser Liste einzelne Teilnehmer zum Vorrechnen von Aufgaben(teilen) ausgesucht. Falls sich beim Vorrechnen herausstellen sollte, dass Sie keine sinnvolle Lösung vorweisen können, obwohl Sie in der Liste Punkte für diese(n) Aufgabe(nteil) eingetragen haben, werden Ihnen für das gesamte gerade behandelte Übungsblatt keine Übungspunkte angerechnet. Eine sinnvolle Lösung muss hierbei nicht notwendigerweise vollständig korrekt sein

 


Prüfung

 

Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungs- und Übungsstunden behandelte Material durchzuarbeiten.

Die Modulabschlussprüfung wird durch eine mündliche Prüfung erfolgen.

Voraussetzung für die Zulassung zur Prüfung ist:

  • Erreichen von mindestens 50 Prozent aller Übungspunkte. Um dies zu gewährleisten empfehlen wir dringend, regelmäßig und aktiv an den Übungsstunden teilzunehmen. Beachten Sie hierzu auch die "Spielregeln" -- und
  • Erreichen von mindestens 40 Prozent der Punkte eines gesonderten Präsenzübungsblattes, welches in der Mitte des Semesters bearbeitet wird.

 


Literatur

 

[1] John E. Hopcroft und Jeffrey D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheotrie. Addison-Wesley, 1993.
[2] Javier Esparza und Michael Blondin: Automata Theory: An Algorithmic Approach. MIT Press, 2023.
[3] Dominique Perrin und Jean-Éric Pin: Infinite Words: Automata, Semigroups, Logic and Games. Academic Press, 2004.
[4] Martin Hofmann und Martin Lange: Automatentheorie und Logik. Springer, 2011.
[5] Hubert Comon et al.: Tree Automata Techniques and Applications. Online verfügbar: http://tata.gforge.inria.fr/
[6] Edmund M. Clarke, Orna Grumberg und Doron A. Peled: Model Checking. MIT Press, 2001.
[7] Jean-Éric Pin: Mathematical Foundations of Automata Theory. Online verfügbar: https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf
[8] Howard Straubing: Model Checking: Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser Boston, MA, 1994.