Seminar über Automatentheorie
» Diese Veranstaltung wird auf deutsch gehalten.
Seminar im Wintersemester 2011/2012
| Art | ECTS | Ort | Veranstalter |
|---|---|---|---|
| S2 | 4 | Seminarraum Lehrstuhl Informatik 7 | Thomas, Löding |
Die Plätze werden im zentralen Vergabeverfahren vergeben.
Allgemeines
In dem Seminar werden Originalarbeiten aus dem Themenumfeld der Vorlesung Angewandte Automatentheorie studiert.Vorwissen
Gute Vorkenntnisse der Automatentheorie, vorzugsweise belegt durch erfolgreiche Teilnahme an Übungen zu Vorlesungen des Lehrstuhls, sind erwünscht.
Ablauf
- Allgemeine Informationen zum Ablauf findet man auf den Folien aus der Vorbesprechung
- Folgende Termine sind neben den Vortragsterminen einzuhalten:
- Erste Absprache mit dem Betreuer bis: 21.10.2011
- Abgabe der Ausarbeitung: bis 3 Wochen vor dem Vortragstermin
- Die Vorträge sollten eine Dauer von ca. 50-55 Minuten haben.
-
Die Vorträge finden im Seminarraum am Lehrstuhl 7 statt. Geplant sind
3 Blöcke an folgenden Terminen:
- Freitag, 20.1.2012
- Freitag, 27.1.2012
- Montag, 6.2.2012
Bei Fragen wenden Sie sich bitte an Christof Löding.
Themen
Die mit (M) gekennzeichneten Themen sind für Teilnehmer aus dem Studiengang M.Sc. Informatik. Die anderen Themen sind für Teilnehmer aus den Studiengängen Informatik B.Sc. und Informatik Lehramt.1. Termin: Freitag, 20.1.2012
-
8:45-9:45 Uhr
Sequentielle Transducer und der Satz von Ginsburg/Rose
Quelle: [Ber79], Abschnitt IV.2; [Eil74], Kapitel XI; [BR99]
Vortrag: Christoph Matheja
Betreuung: W. Fridman -
9:45-10:45 Uhr
Cross-Section-Theorem und nicht-mehrdeutige Transducer
Quelle: [Ber79], Abschnitte IV.3-4
Vortrag: Jera Hensel
Betreuung: W. Thomas -
10:45-11:45 Uhr
Bimaschinen
Quelle: [Ber79], Abschnitt IV.5
Vortrag: Stefan Schubert
Betreuung: W. Thomas -
11:45-12:45 Uhr
Rationale Relationen mit beschränkter Verzögerung (M)
Quelle: [FS91]
Vortrag: Gereon Kremer
Betreuung: W. Fridman
2. Termin: Freitag, 27.1.2012
- 9-10 Uhr
Synchronisation in Automaten
Quelle: [Vol08]
Vortrag: Alexander Weinert
Betreuung: J. Olschewski
- 10-11 Uhr
Transducer mit Speicher (M)
Quelle: [Alu11]
Vortrag: Katrin Hölldobler
Betreuung: W. Thomas - 11-12 Uhr
Determinisierung von Wort-Transducern (M)
Quelle: [Moh97]
Vortrag: Jonathan Meyer
Betreuung: C. Löding
- 12-13 Uhr
Minimierung von Wort-Transducern (M)
Quelle: [Moh97]
Vortrag: Sebastian Mühr
Betreuung: C. Löding
3. Termin: Montag, 6.2.2012
- 9-10 Uhr
Äquivalenztest für eindeutige NEAs (M)
Quelle: [SH85]
Vortrag: Helge Reelfs
Betreuung: J. Olschewski
- 10-11 Uhr
4-Wege-Automaten und Tiling-Systeme
Quelle: [GR97]
Vortrag: Angelika Schwarz
Betreuung: N. Chaturvedi
- 11-12 Uhr
Rationale Graphen und konstextsensitive Sprachen
Quelle: [CM06]
Vortrag: Aleksandr Grinspun
Betreuung: N. Chaturvedi
- 13-14 Uhr
Eine logische Charakterisierung der kontextfreien Sprachen
Quelle: [LST94]
Vortrag: Laura Tiemann
Betreuung: S. Schulz
- 14-15 Uhr
Alternative logische Charakterisierungen der regulären Sprachen (M)
Quelle: [Pot94]
Vortrag: Benjamin Kaminski
Betreuung: S. Schulz
Quellen
| [Alu11] | Rajeev Alur, Jyotirmoy V. Deshmukh: Nondeterministic Streaming String Transducers. ICALP 2011, Lecture Notes in Computer Science 6756, pp. 1-20, Springer, 2011. |
| [Ber79] | J. Berstel Transductions and Context-Free Languages. Teubner-Verlag, 1979. |
| [BR99] | Véronique Bruyère, Christophe Reutenauer. A Proof of Choffrut's Theorem on Subsequential Functions. Theoretical Computer Science, volume 215(1-2), p. 329-335, 1999. |
| [CM06] | A. Carayol, A. Meyer: Context-Sensitive Languages, Rational Graphs and Determinism. Logical Methods in Computer Science, vol 2(2), 2006. |
| [Eil74] | S. Eilenberg. Automata, Languages, and Machines, vol A. Academic Press, 1974. |
| [FS91] | C. Frougny, J. Sakarovitch. Rational Relations with Bounded Delay. STACS 91, 8th Annual Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, February 14-16, 1991, Proceedings Lecture Notes in Computer Science 480, pp. 50-63, Springer, 1991. |
| [GR97] | D. Giammarresi, A. Restivo: Two-dimensional Languages. In Handbook of Formal Languages, G. Rosenberg and A. Salomaa (Eds), Vol. III, Seite 215-268. Springer Verlag, 1997. |
| [LST94] | Clemens Lautemann, Thomas Schwentick, Denis Thérien: Logics For Context-Free Languages. Computer Science Logic, 8th International Workshop, CSL '94, Kazimierz, Poland, September 25-30, 1994, Selected Papers. Lecture Notes in Computer Science 933 Springer 1995 |
| [Moh97] | Mehryar Mohri. Finite-state transducers in language and speech processing. Comput. Linguist., 23(2):269 |
| [Pot94] | Andreas Potthoff. Logische Klassifizierung regulärer Baumsprachen. Dissertation, Christian-Albrechts-Universität Kiel, 1994. |
| [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) |
| [Vol08] | Mikhail V. Volkov: Synchronizing Automata and the Cerny Conjecture. Language and Automata Theory and Applications, Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers. Lecture Notes in Computer Science 5196 Springer 2008. |