Logic and
Theory of
Discrete Systems

Informatik 7

Seminar über Automatentheorie (Wintersemester 2015/16)

Inhalt

Gegenstand dieses Seminars sind Originalarbeiten und Überblicksartikel zur Automatentheorie, voraussichtlich mit einem Schwerpunkt im Umkreis der Vorlesung Applied Automata Theory). Aktive Teilnahme an dieser Vorlesung (oder vergleichbaren Vorlesungen in früheren Semestern) inklusive Übung ist hilfreich zur Bearbeitung der Themen und wird bei der Zuteilung von Plätzen berücksichtigt.

Es handelt sich um ein Seminar in der theoretischen Informatik. Es wird entsprechend von den Teilnehmern der Umgang mit abstrakten Modellen und mathematischen Beweisen erwartet.

Ablauf und Termine

  • Allgemeine Informationen zum Ablauf werden in der Vorbesprechung bekanntgegeben. [Folien aus der Vorbesprechung]
  • Der Rücktritt von dem Seminar ohne Eintragung eines Fehlversuchs ist bis zu 3 Wochen nach der Vorbesprechung möglich, also bis zum 29.9.2015.
  • Das Seminar findet an drei Blockterminen zum Ende der Vorlesungszeit statt (siehe unten).
  • Die Vorträge sind im Seminarraum am Lehrstuhl 7.

Bei Fragen wenden Sie sich an Christof Löding.

Themen

Dienstag, 26. Januar 2016, 13-17 Uhr

  • 13 Uhr: Aktives Lernverfahren nach Kearns/Vazirani (Quelle: [KV94]; Betreuung: Christof Löding; Vortrag: Schraut, Thomas)

  • 14 Uhr: Lernverfahren für reguläre Ausdrücke (Quelle: [BGNV08], [Fer09]; Betreuung: Christof Löding; Vortrag: Plum, Alexander)

  • 15 Uhr: Äquivalenztest für eindeutige NEAs (Quelle: [SH85]; Betreuung: Sarah Winter; Vortrag: Langer, Andrea)

  • 16 Uhr: Deterministische reguläre Ausdrücke (Quelle: [BKW98]; Betreuung: Christof Löding; Vortrag: Rogoll, Torsten)

Montag, 1. Februar 2016, 10-13 Uhr

  • 10 Uhr: Der Universal-NEA (Quelle: [LS08]; Betreuung: Christof Löding; Vortrag: Wilke, Richard)

  • 11 Uhr: Regular Sensing (Quelle: [AKK14]; Betreuung: Christof Löding; Vortrag: Gierse, Gesche)

  • 12 Uhr: Determinisierung von Wort-Transducern (Quelle: [BC02]; Betreuung: Sarah Winter; Vortrag: Fortmann, Jonas)

Dienstag, 2. Februar 2016, 13-16 Uhr

  • 13 Uhr: Synchronisationssprachen für Wortrelationen (Quelle: [FL14]; Betreuung: Christof Löding; Vortrag: Kabelitz, Marco)

  • 14 Uhr: Lineare Automaten und Cache-Kohärenz (Quelle: [EK12]; Betreuung: Christof Löding; Vortrag: Mitev, Kiril)
  • 15 Uhr: Automaten mit  Kapazitätsschranken (Quelle: [KT14], Betreuung: Christof Löding; Vortrag: Carsten von den Driesch)

Quellen

Die Quellen findet man in der Informatik-Bibliothek und zum Teil auch im Internet. Auf die offiziellen elektronischen Veröffentlichungen der Verlage kann man oft nur aus dem RWTH-Netz zugreifen.

[AKK14] Shaull Almagor, Denis Kuperberg, Orna Kupferman. Regular Sensing. FSTTCS 2014: 161-173. LIPIcs 29, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2014
[BC02]
Marie-Pierre Béal, Olivier Carton. Determinization of transducers over finite and infinite words. Theoretical Computer Science, Volume 289, Issue 1, 23 October 2002, Pages 225–251
[BGNV08] Geert Jan Bex, Wouter Gelade, Frank Neven, Stijn Vansummeren: Learning deterministic regular expressions for the inference of schemas from XML data. Proceedings of the 17th International Conference on World Wide Web, WWW 2008
[BKW98] Anne Brüggemann-Klein, Derick Wood: One-Unambiguous Regular Languages. Inf. Comput. 140(2): 229-253 (1998)
[EK12] J. Esparza, J. Kreiker: Three Case Studies on Verification of Infinite-State Systems. Kapitel 12 in Modern Applications of Automata Theory. Deepak D'Souza and Priti Shankar (editors), World Scientific, 2012.
 [Fer09]  H. Fernau:Algorithms for learning regular expressions from positive data. Information and Computation Volume 207, Issue 4, April 2009, Pages 521–541
 [FL14]  Diego Figueira, Leonid Libkin. Synchronizing Relations on Words. STACS 2014: 518-529. LIPIcs 25, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2014
[KT14] Orna Kupferman, Tami Tamir. Properties and Utilization of Capacitated Automata (Invited Talk). FSTTCS 2014: 33-44. LIPIcs 29, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2014
 [KV94]  M.J. Kearns, U.V. Vazirani An Introduction to Computational Learning Theory. MIT Press, 1994.
 [LS08]   Sylvain Lombardy, Jacques Sakarovitch: The universal automaton In: Jörg Flum, Erich Grädel and Thomas Wilke: Logic and Automata - History and Perspectives, Text in Logic and Games Volume 2, pp. 457-504, Amsterdam University Press, 2008.
 [SH85] Richard Edwin Stearns, Harry B. Hunt III: On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata. SIAM J. Comput. 14(3): 598-611 (1985)
FaLang translation system by Faboba