Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2017/18 / Master-Seminar: Automatentheorie


Inhaltsbereich

Master-Seminar: Automatentheorie

Masterseminar, Barth

Aktuelles

  • Die Anmeldung erfolgt über die Zentralanmeldung für Masterseminare auf UniWorX.
  • Die Vorbesprechung mit Themenvergabe findet am Freitag, den 20.10.2017 von 13 bis 14 Uhr im Raum L109, Oettingenstr. 67 statt.

Inhalt

Die Automatentheorie liefert mit dem abstrakten Konzept eines Automaten und verschiedenen Konkretisierungen dieses Konzepts eine Reihe an nützlichen Algorithmen und Datenstrukturen für sehr verschiedenartige Problemstellungen, zum Beispiel in der Verifikation, im Lernen oder Parsen von Daten. Dieses Seminar behandelt einige dieser vertiefenden Themen der Automatentheorie. Mögliche Themengebiete sind: Automaten in der Verifikation (LTL), verschiedenes zur Minimierung von Automaten, Brozowski-Ableitungen, Lernen von Automaten, Hybride Automaten, gewichtete Automaten, Transfinite Automaten, Konvertierungen zwischen Automatenmodellen, Komplementierungen von Automaten, Alternierende Automaten, 2-way Automaten, tree-walking Automaten, visibly push-down Automaten.


Organisation

Anforderungen

  • Blitzvortrag 90 Sekunden: Inhaltsübersicht, eine Folie
  • Vortrag: 30 Minuten (plus Diskussion)
  • Anwesenheit während der Seminarsitzungen
  • Ausarbeitung zum Thema (20.000-30.000 Zeichen)

Zeit und Ort

  • Zeitplan und Themen werden in einer Vorbesprechung zu Semesterbeginn mit den Teilnehmern festgelegt.
  • Vorbesprechung: Fr, 20.10.2017, 13-14
  • Blitzvorträge: Fr, 3.11.2017 (Reservetermin 17.11.), 18st; Raum L109
  • Abgabe Ausarbeitung (Vorabversion): 31.12.2017
  • Abgabe Reviews: 23.01.2018
  • Seminar: 19.02.2018-23.02.2018
  • Abgabe Ausarbeitung (Endfassung): 05.03.2018

Themen

 Themenzuteilung

ThemaBearbeiterBetreuer
Hopcroft EL Stephan Barth
DFA-minvergleich AM Stephan Barth
Brzozowski Ableitungen DH Christian Neukirchen
DFA-learning TN Stephan Barth
Visibly Pushdown BH Stephan Barth
Mehr Modelle LK Stephan Barth
LTL -> Büchi PL Stephan Barth

 

Literatur

  • Brzozowski Ableitungen
       Brzozowski Ableitungen bauen Automaten aus Linksableitungen von
       zugrundeliegenden Sturkturen auf.
       Hier wird die direkte Konstruktion eines endlichen Automatens aus
       regulären Ausdrücken behandelt. Ferner wird noch gezeigt, wie man
       mithilfe von partiellen Brzozowski Ableitungen ein Wort, welches
       von einem regulären Ausdruck erkannt wird, in die Wortteile zerlegt,
       die zu den Teilausdrücken des regulären Ausdrucks passen.
       Paper: Derivatives of Regular Expressions, JANUSZ A. BRZOZOWSKI
       Paper: Regular Expression Sub-Matching using Partial Derivatives, Martin Sulzmann, Kenny Zhuo Ming Lu
    Paper: Regular-expression derivatives reexamined, SCOTT OWENS, JOHN REPPY, AARON TURON
  • Visibly Pushdown
       Visibly pushdown Automaten liegen in ihren Möglichkeiten zwischen
       regulären und kontextfreien Sprachen. Es handelt sich dabei um
       die bekannten pushdown-Automaten, bei denen aber zusätzlich direkt am
       Alphabet erkannt werden kann, welche Stackoperation sie durchführen.
       Dieser Vortrag beinhaltet die Definition und einige Algorithmen auf
       Visibly pushdown Automaten.
       Paper: Visibly Pushdown Languages, Rajeev Alur, P. Madhusudan
  • Mehr Modelle
       Automaten können erweiterte Eigenschaften haben, welche es ermöglicht sie
       in anderen Szenarien einzusetzen. Drei dieser erweiterten Modelle sollen
       hier kurz präsentiert werden, zudem sollen grundlegende Algorithmen und
       Eigenschaften angesprochen werden:
        + Transducer: Diese lesen nicht nur ein Wort, sondern geben auch wieder
          ein Wort aus
          https://en.wikipedia.org/wiki/Finite-state_transducer
          Paper: The Decidability of Equivalence for Deterministic Finite Transducers, Meera Blattner, Tom Head
        + weighted automaton: Diese berechnen zum gelesenen Wort ein Gewicht
          Paper: Weighted Automata Algorithms, Mehryar Mohri
        + hybride Automaten: Diese stellen eine Verschmelzung von Automaten
          mit endlichem Zustandsraum mit Differentialgleichungen dar
          Paper: HyTech : A Model Checker for Hybrid Systems, Thomas A. Henzinger, 2Pei-Hsin Ho, Howard Wong-Toi
          Paper: The Theory of Hybrid Automata, Thomas A. Henzinger
  • Hopcroft
       Über den Minimierungsalgorithmus von Hopcroft:
       DFA-Minimierung in n log n.
       Vortrag über: Algorithmus, Beweis der Laufzeit und Koorektheit. Hinweise
       zur effizienten Implementierung.
       Ausblick auf Hopcroft für endliche Bäume
       https://en.wikipedia.org/wiki/DFA_minimization#Hopcroft.27s_algorithm
       Paper: Describing an Algorithm by Hopcroft, David Gries
       Paper: An O(n log n) implementation of the standard method for minimizing n-state finite automata, Norbert Blum
       Paper: Efficient Implementation for Deterministic Finite Tree Automata Minimization, Younes Guellouma, Hadda Cherroun
  • DFA-minvergleich
       Vergleich verschiedener Minimierungsalgorithmen für DFA. Vorstellung der
       Algorithmen, die verglichen werden (bis auf Hopcroft) sowie der
       Ergebnisse.
       Paper: On the Performance of Automata Minimization Algorithms, Marco Almeida, Nelma Moreira, and Rogerio Reis
       darin: Algorithmen B W WD erklären, Vergleich präsentieren
  • DFA-learning
       Einen Automaten zu lernen bedeutet ihn aus Wörtern sowie der Information,
       ob diese von dem Automaten akzeptiert werden sollen, zu berechnen.
       Dieser Vortrag stellt das grundlegende Lernverfahren von Angluin für
       DFA vor, sowie die Erweiterung auf endliche Baumautomaten.
       Paper: Learning Regular Sets from Queries and Counterexamples, Angluin
       Paper: Learning tree languages from positive examples and membership queries, Jerome Besombes, Jean-Yves Marion
  • LTL -> Büchi
       https://en.wikipedia.org/wiki/Linear_temporal_logic
       https://en.wikipedia.org/wiki/Linear_temporal_logic_to_B%C3%BCchi_automaton
       Ebenso die dort verlinkten Quellen
       Paper: Limit-Deterministic Büchi Automata for Linear Temporal Logic, Salomon Sickert, Javier Esparza, Stefan Jaax, and Jan Kretinsky
       Spin-Modelchecker






 

 


Weitere Informationen

Tipps zum Aufbau von Vorträgen und zu Präsentationstechniken:

 

Artikelaktionen


Funktionsleiste