Seminar FGI 3 im Wintersemester 2014/15
Erste Freitagsgruppe

Termin: Fr 12:15-13:45 in D-220

Vorträge

Ablauf

• Die Vorträge finden in der Regel in Zweiergruppen statt. Üblicherweise sind die Vorträge auf Deutsch; in Einzelfällen kann auch auf Englisch vorgetragen werden.
• Pro Vortragendem/-er sind ca. 30 Minuten Vortragszeit zu veranschlagen.
• Alle Vortragenden sollen mindestens einen Beweis an der Tafel präsentieren.
• Nach dem Vortrag findet eine kleine Diskussion über das Thema statt. Hierbei sollten Sie durch eigene Beiträge aktiv mitwirken.
• Eine Woche vor Ihrem Vortrag sollten Sie den Veranstalter kontaktieren und berichten, wie Sie planen, Ihren Vortrag aufzubauen.
• Spätestens am 9. Februar 2015 ist eine ca. 5-seitige Ausarbeitung Ihres Vortrags beim Veranstalter abzugeben (elektronisch als pdf). Eine Vorlage für die Ausarbeitung (mit LaTeX) finden Sie hier (vom Wintersemester 2012/2013).
• Es besteht Anwesenheitspflicht. Sollten Sie an einem der Termine verhindert sein, dann melden Sie sich beim Veranstalter ab. Ab einschließlich dem dritten Fernbleiben müssen Sie ein ärztliches Attest vorlegen. Sollten Sie bei Ihrem eigenen Vortrag nicht am Seminar teilnehmen können, wird für die Teilnahme am Seminar kein Schein vergeben.

Literatur

1. D. Angluin: Learning Regular Sets from Queries and Counter-Examples. Information and Control 75, pp. 87–106, 1987.
2. J. Berstel, L. Boasson, O. Carton, I. Fagnot: Minimization of Automata. arXiv:1010.5318, 2010.
3. D. C. Cooper: Theorem Proving in Arithmetic without Multiplication, in B. Meltzer and D. Michie, eds., Machine Intelligence Vol. 7. Edinburgh University Press, pp. 91–99, 1972.
4. V. Diekert, P. Gastin: First-order definable languages. In Logic and Automata: History and Perspectives, Texts in Logic and Games 2, pp. 261-306. Amsterdam University Press, 2008. Technischer Bericht
5. V. Diekert, M. Kufleitner, G. Rosenberger: Diskrete Algebraische Methoden, Walter de Gruyter, 2013. Campus Lizenz
6. J. Esparza: Automata Theory: An Algorithmic Approach. 2012.
7. J. E. Hopcroft, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley, 1979.
8. M. Kufleitner: Automata and Formal Languages. Lecture Notes WS 2013/2014, Technische Universität München, 2014.
9. D. C. Oppen: A 2^22pn Upper Bound on the Complexity of Presburger Arithmetic. In: J. Comput. Syst. Sci. 16(3), pp. 323–332, 1973.
10. W. Thomas: Automata on infinite objects. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B: Formal Models and Semantics, pages 133-192. Elsevier Science Publishers, Amsterdam, 1990. Technischer Bericht.
11. W. Thomas: Languages, automata, and logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume III, pages 389-455. Springer, New York, 1997. Technischer Bericht
12. W. Zielonka: Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoretical Computer Science, 200(1-2):135-183, 1998. Technischer Bericht

Zuordnung zu den Vorträgen

• 31.10.2014: [7, Seiten 336ff]
• 07.11.2014: [3], ein Blick in [9] kann nützlich sein
• 14.11.2014: [5, Abschnitt 7.6]
• 21.11.2014: Die entsprechenden Abschnitte aus [2] und [8]
• 28.11.2014: [1] und der entsprechende Abschnitt aus [8]
• 12.12.2014: [6, Abschnitt 7]
• 19.12.2014: [10] sowie [5, Satz 6.6]
• 09.01.2015: [5, Abschnitt 7.7.3, Aufgabe 7.13, Aufgabe 7.14], eventuell kann ein Blick in [5, Abschnitt 7.1] hilfreich sein
• 16.01.2015: Die entsprechenden Abschnitte aus [4]
• 23.01.2015: [12]
• 30.01.2015: [11, Abschnitt 6]