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

Lehrveranstaltungen:

• • Algebraische und Logische Aspekte der Automatentheorie
    (Vorlesung mit Übung, 4 SWS, Stefan Milius, Mi, 12:15 - 13:45, 01.255-128; Do, 08:15 - 09: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 2018/2019)
Berechenbarkeit und Formale Sprachen (WS 2018/2019)

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:

Fachkompetenz

Wissen

Die Studierenden geben elementaren Definitionen, Begriffe und Fakten der algebraischen Sprachtheorie wieder.

Verstehen

Die Studierenden

• erläutern grundlegende Begriffe der Halbgruppentheorie und der Topologie

• erklären die Äquivalenz zwischen monadischer Logik 2. Stufe und regulären Sprachen

• erklären die Äquivalenz zwischen Monoid erkennbaren und regulären Sprachen

Anwenden

Die Studierenden

• beschreiben mit Hilfe von logischen Formeln formale Sprachen

• konstruieren algebraische Erkenner für reguläre Sprachen

• spezifizieren Klassen von regulären Sprachen durch Folgen von Gleichungen oder proendliche Gleichungen

Analysieren

Die Studierenden analysieren mathematische Beweise, diskutieren die entsprechenden Argumentationen und legen diese schriftlich nieder.

Evaluieren (Beurteilen)

Die Studierenden

• ermitteln, ob eine vorgelegte Sprache durch die Logik erster Stufe beschreibbar ist

Erschaffen

Die Studierenden

• entwickeln eine logische Sichtweise für weitere Automatenmodelle und Typen von formalen Sprachen.

• arbeiten Korrespondenzen zwischen Automatenmodellen und algebraischen Strukturen aus.

Lern- bzw. Methodenkompetenz

Die Studierenden

• beherrschen das grundsätzliche Konzept des Beweises als hauptsächliche Methode des Erkenntnisgewinns in der theoretischen Informatik. Sie überblicken abstrakte Begriffsarchitekturen.

• vollziehen mathematische Argumentationen nach, erklären diese, führen diese selbst und legen sie schriftlich nieder.

Sozialkompetenz

Die Studierenden lösen Probleme in kollaborativer Gruppenarbeit und präsentieren erarbeitete Lösungen.

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 (Master of Science)
   (Po-Vers. 2010 | TechFak | Informatik (Master of Science) | Wahlpflichtbereich | Säule der theoretisch orientierten Vertiefungsrichtungen | Vertiefungsrichtung Theoretische Informatik | Algebraische und Logische Aspekte der Automatentheorie)

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

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

1. Prüfer:

Stefan Milius

Ort: Martenstr. 3, 11. Stock, Raum 11.152