Seminar über Automatentheorie
» Diese Veranstaltung wird auf deutsch gehalten.
Inhalt
Gegenstand dieses Seminars sind Originalarbeiten und Überblicksartikel zur Automatentheorie, voraussichtlich mit einem Schwerpunkt im Umkreis der Vorlesung Infinite Computations des WS 2011/12 (die Themen werden in Abhängigkeit der Vorkenntnisse der Teilnehmer evtl. angepasst). 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.
Ablauf und Termine
- Allgemeine Informationen zum Ablauf findet man auf den Folien aus der Vorbesprechung
- Das Seminar wird an zwei oder drei Terminen zum Ende der Vorlesungszeit stattfinden.
- Folgende Termine sind neben den Vortragsterminen einzuhalten:
- Erste Absprache mit dem Betreuer bis spätestens 13.4.2012
- Abgabe der Ausarbeitung: spätestens 3 Wochen vor dem Vortrag
Bei Fragen wenden Sie sich bitte an Christof Löding.
Vorträge
1. Termin: Freitag, 29.6.2012
- 14-15 Uhr
Büchi-Automaten auf festen omega-Wörtern I
Quelle: [ER66]
Vortrag: Kevin Jasik
Betreuung: W. Fridman
- 15-16 Uhr
Locally testable languages (in english)
Quelle: [Boj07]
Vortrag: Moses Ganardi
Betreuung: N. Chaturvedi
2. Termin: Freitag, 13.7.2012
- 10-11 Uhr
Automaten mit strukturierten unendlichen Alphabeten
Quelle: [Bès08]
Vortrag: Paul Dingil
Betreuung: W. Thomas
3. Termin: Dienstag, 17.7.2012
- 9-10 Uhr
Eine Charakterisierung von Pushdown-Graphen
Quelle: [MS85]
Vortrag: anonym
Betreuung: S. Repke
- 10-11 Uhr
Eingabegesteuerte Pushdown-Transducer
Quelle: [FRRS10]
Vortrag: Kim Haps
Betreuung: S. Repke
- 11-12 Uhr
Lernen von Automaten ohne Reset des Orakels
Quelle: [RS89]
Vortrag: Karola Weischenberg
Betreuung: C. Löding
- 12-13 Uhr
Lernen von Automaten aus kürzesten Gegenbeispielen
Quelle: [BBS98]
Vortrag: Dominik Hurtienne
Betreuung: C. Löding
Quellen
Die Quellen findet man im Internet oder in der Bibliothek. Beschaffung der Literatur ist Teil des Seminars.
| [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 |
| [Bès08] | Alexis Bès: An application of the Feferman-Vaught Theorem to Automata and Logics for words over an infinite alphabet, Logical Methods in Comput. Sci., Vol 4(2008), 1-23. [Sections 1-3] |
| [Boj07] | Mikolaj Bojanczyk: A new algorithm for testing if a regular language is locally threshold testable. Inf. Process. Lett. 104(3): 91-94 (2007) |
| [Col11] | Thomas Colcombet. Green's Relations and Their Use in Automata Theory. In LATA, pages 1-21, 2011. |
| [CT02] | O. Carton and W. Thomas. The monadic theory of morphic infinite words and generalizations. Information and Computation, 176:51-76, 2002. |
| [ER66] | Calvin C. Elgot and Michael O. Rabin. Decidability and Undecidability of Extensions of Second (First) Order Theory of (Generalized) Successor. J. Symbolic Logic Volume 31, Issue 2 (1966), 169-181. |
| [FRRS10] | Emmanuel Filiot, Jean-François Raskin, Pierre-Alain Reynier, Frédéric Servais, Jean-Marc Talbot: Properties of Visibly Pushdown Transducers. MFCS 2010: 355-367 |
| [KF94] | Michael Kaminski, Nissim Francez: Finite-Memory Automata. Theor. Comput. Sci. 134(2): 329-363 (1994) |
| [MS85] | David E. Muller, Paul E. Schupp: The Theory of Ends, Pushdown Automata, and Second-Order Logic. Theor. Comput. Sci. 37: 51-75 (1985) |
| [NS99] | Frank Neven, Thomas Schwentick. Query Automata. Proceedings of the of the Eighteenth ACM Symposium on Principles of Database Systems, pages 205-214, 1999. |
| [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. |
| [STV01] | Thomas Schwentick, Denis Thérien, Heribert Vollmer: Partially-Ordered Two-Way Automata: A New Characterization of DA. Developments in Language Theory 2001: 239-250 |