Logic and
Theory of
Discrete Systems

Informatik 7

Seminar über Automatentheorie (Wintersemester 2014/15)

Inhalt

Gegenstand dieses Seminars sind Originalarbeiten und Überblicksartikel zur Automatentheorie, voraussichtlich mit einem Schwerpunkt im Umkreis der Vorlesung Angewandte Automatentheorie). 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 findet man auf den Folien aus der Vorbesprechung.
  • Das Seminar findet an zwei Blockterminen statt (siehe unten).
  • Die Vorträge sind im Seminarraum am Lehrstuhl 7.

Bei Fragen wenden Sie sich an Christof Löding.

Themen

 Mittwoch 21.1.2015: Lernverfahren für reguläre Sprachen

  • 10 Uhr: Aktives Lernverfahren nach Kearns/Vazirani
    Quelle: [KV94]
    Vortrag: Hanna Kahlfeld
    Betreuung: Martin Lang
     
  • 11 Uhr: Aktives Lernen ohne Reset des Orakels
    Quelle: [RS89]
    Vortrag: Martin Wohnout
    Betreuung: Martin Lang
      
  • 12 Uhr: Das PAC-Modell: Stichproben statt Äquivalenzanfragen
    Quelle: [Ang87], [Val84], [KV94]
    Vortrag: Christian Schmidt
     Betreuung: Christof Löding
      
  • 14:30 Uhr: Aktives Lernen aus kürzesten Gegenbeispielen
    Quelle: [BBS98]
    Vortrag: Hilke Buss
    Betreuung: Sarah Winter
      
  • 15:30 Uhr: Lernverfahren für Automaten über großen Alphabeten
    Quelle: [MM14]
    Vortrag: Robin Rogner
    Betreuung: Christof Löding
      
  • 16:30 Uhr: Lernverfahren für reguläre Ausdrücke
    Quelle: [BGNV08], [Fer09]
    Vortrag: Lukas Huwald
    Betreuung: Christof Löding 
      

Mittwoch 28.1. 2015: Automaten in der Verifikation 

  • 10 Uhr: Automaten mit Zeitbedingungen und ein Mutex-Protokoll
    Quelle: [EK12]
    Vortrag: Alex Lorenz
    Betreuung: Benedikt Brütsch
      
  • 11 Uhr: Lineare Automaten und Cache-Kohärenz
    Quelle: [EK12]
    Vortrag: Eva Fluck
    Betreuung: Benedikt Brütsch
       
  • 12 Uhr: Wohlstrukturierte Transitionssysteme mit Hilfsspeicher
    Quelle: [CV07]
    Vortrag: Maik Lühmann
    Betreuung: Sarah Winter
      
  • 14:30 Uhr: Boolsche Programme und Pushdownautomaten
    Quelle: [KMV06]
    Vortrag: Marco Grochowski
    Betreuung: Christof Löding
      
  • 15:30 Uhr: Symbolische Visibly-Pushdown-Automaten
    Quelle: [DA14]
    Vortrag: Manuel Krebber
    Betreuung: Christof Löding
  • 16:30 Uhr: Lernverfahren für Registerautomaten
    Quelle: [HSJC12]
    Vortrag: Reza Nazeman
    Betreuung: Christof Löding

Quellen

Die Quellen findet man in der Bibliothek und zum Teil auch im Internet.

[Ang81]

Dana Angluin: A Note on the Number of Queries Needed to Identify Regular Languages. Information and Control 51, 76-87, 1981

[Ang87] D. Angluin: Learning regular sets from queries and counterexamples, Information and Computation 75: 87-106 (1987)
[Ang90]

Dana Angluin. Negative results for equivalence queries. Machine Learning, 5:121-150, 1990.

[BBS98] Andreas Birkendorf, Andreas Böker, Hans-Ulrich Simon: Learning Deterministic Finite Automata from Smallest Counterexamples. Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998: 599-608
[BDG97] Jose L. Balcazar, Josep Diaz, and Ricard Gavalda. Algorithms for learning finite automata from queries: A uni ed view. In Advances in Algorithms, Languages, and Complexity, pages 53-72, 1997.
[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
[CV07] R. Chadha, M. Viswanathan: Decidability Results for Well-Structured Transition Systems with Auxiliary Storage, International Conference on Concurrency Theory (CONCUR), 2007.
[DA14] L. D'Antoni and R. Alur. Symbolic Visibly Pushdown Automata, 26th International Conference on Computer-Aided Verification, 2014
[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

[Gol78] E.M. Gold Complexity of Automaton Identification from Given Data. Information and Control, volume 37, p. 302-320, 1978.
[HSJC12]

Falk Howar, Bernhard Steffen, Bengt Jonsson, Sofia Cassel: Inferring Canonical Register Automata. VMCAI'12 Proceedings of the 13th international conference on Verification, Model Checking, and Abstract Interpretation Pages 251-26. Springer 2012

[KMV06] V. Kumar, P. Madhusudan, M.Viswanathan: Minimization, Learning, and Conformance Testing of Boolean Programs, International Conference on Concurrency Theory (CONCUR), 2006.
[KV94] M.J. Kearns, U.V. Vazirani An Introduction to Computational Learning Theory. MIT Press, 1994.
[MM14] O. Maler, I.E. Mens, Learning Regular Languages over Large Alphabets, Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2014, Springer 2014 Lecture Notes in Computer Science.
[OG92] Jose Oncina and Pedro Garca. Identifying regular languages in polynomial time. In Proceedings of the International Workshop on Structural and Syntactic Pattern Recognition, volume 5 of Machine Perception and Arti cial Intelligence, pages 99-108. World Scienti c, 1992.
[RS89] Rivest R. L., and Schapire, R. E. 1989. Inference of finite automata using homing sequences. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Inf. Comput. ACM, New York. 299-347.
[Val84] L. Valiant. A theory of the learnable. Communications of the ACM, 27, 1984.