Algebraische und Logische Aspekte der Automatentheorie (ALoA)7.5 ECTS
(englische Bezeichnung: Algebraic and Logical Aspects of Automata Theory)
(Prüfungsordnungsmodul: Vertiefungsrichtung Theoretische Informatik)

Lehrveranstaltungen:

• • Algebraische und Logische Aspekte der Automatentheorie
    (Vorlesung mit Übung, 4 SWS, Henning Urbat et al., Mo, 10:15 - 11:45, 01.255-128; Mi, 12:15 - 13:45, 01.255-128)

Empfohlene Voraussetzungen:

Es wird empfohlen, folgende Module zu absolvieren, bevor dieses Modul belegt wird:

Grundlagen der Logik in der Informatik (WS 2017/2018)
Berechenbarkeit und Formale Sprachen (WS 2017/2018)

Inhalt:

Automaten als mathematische Formalisierung zustandsbasierter Systeme gehören zu den wichtigsten Werkzeugen der Theoretischen Informatik und besitzen zahlreiche Anwendungen, von der Compilerentwicklung bis zur Verifikation reaktiver Systeme. In dieser Veranstaltung, die an die Anfängervorlesungen des Informatikstudiums anknüpft, werden wichtige Querverbindungen zwischen der Automatentheorie und Gebieten der Mathematik (Algebra, Topologie und Logik) hergestellt. Folgende Themen werden behandelt:

• Erkennung von regulären Sprachen durch Monoide und Halbgruppen
  

• Proendliche Gleichungen und Varietäten von Sprachen
  

• Logische Beschreibung regulärer Sprachen, Ehrenfeucht-Fraïssé-Spiele
  

• Automaten, Algebra und Logik auf unendlichen Wörtern und Bäumen

Lernziele und Kompetenzen:

Die Studierenden lernen die algebraische und logische Sichtweise der Automatentheorie kennen und können diese auf verschiedene Automatenmodelle und Typen von formalen Sprachen anwenden.
Die Studierenden machen sich mit mathematischen Grundlagen aus der Halbgruppentheorie und der Topologie vertraut.
Die Studierenden erlangen die Fähigkeit, auf Basis dieser Grundlagen mathematische Beweise zu führen und die entsprechenden Argumente klar schriftlich niederzulegen.

Literatur:

• J.-E. Pin: Mathematical Foundations of Automata Theory
  

• D. Perrin, J.-E. Pin: Infinite Words, Academic Press, 2004
  

• H. Straubing: Finite Automata, Formal Logic, and Circuit Complexity, Birkhäuser, 1994
  

• E. Grädel, W. Thomas, T. Wilke: Automata, Logic, and Infinite Games, Springer, 2002

Bemerkung:

Webseite der Lehrveranstaltung: https://www8.cs.fau.de/course:aloa

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Informatik (Bachelor of Science)
   (Po-Vers. 2009w | TechFak | Informatik (Bachelor of Science) | Wahlpflichtbereich (5. und 6. Semester) | Wahlpflichtmodule | Vertiefungsrichtung Theoretische Informatik)

Studien-/Prüfungsleistungen:

Algebraische und Logische Aspekte der Automatentheorie (Prüfungsnummer: 787141)

(englischer Titel: Algebraic and Logical Aspects of Automata Theory)

Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet, 7.5 ECTS

Anteil an der Berechnung der Modulnote: 100.0 %

Prüfungssprache: Deutsch oder Englisch

Erstablegung: WS 2018/2019, 1. Wdh.: SS 2019 (nur für Wiederholer)

1. Prüfer:

Stefan Milius