Seminar Automatentheorie

» This course is given in German.

Seminar im Sommersemester 2001

ArtTermine/OrtVeranstalter
S2 Do 11:00 - 12:30 4116 Thomas, Wöhrle

Inhalt

Thema des Seminars: Hierarchien und verteilte Transitionssysteme

Termine und Themen

  1. Alternierende Automaten und Concurrency

    Vortrag: Eiko Heuer
    Termin: 19.04.01

  2. Alternierende Automaten auf Bildern

    Vortrag: Chang Pae O
    Termin: 23.04.01

  3. Alternierende Automaten und LTL

    Vortrag: Marc Wolter
    Termin: 30.04.01

  4. Minimierung von Büchi-Automaten

    Vortrag: Anahita Afshin Nia
    Termin: 07.05.01

  5. CTL und alternierende Automaten

    Vortrag: Matthias Egerland
    Termin: 14.05.01

  6. Nonemptiness-Problem für alternierende Automaten

    Vortrag: Ufuk Kefali
    Termin: 21.05.01

  7. Symbolisches/Concurrent Model Checking

    Vortrag: Eike Lang
    Termin: 28.05.01

  8. On-the-y Model Checking

    Vortrag: Norbert Töpker
    Termin: 11.06.01

  9. Reversal-Bounded Multicounter Machines

    Vortrag: Patrick Hütten
    Termin: 18.06.01

  10. Infinite State Transitionssysteme

    Vortrag: Ilia Morgunov
    Termin: 25.06.01

  11. Zellulare Automaten - Game of Life und Turingmächtigkeit

    Vortrag: Simon Kirstein
    Termin: 02.07.01

  12. Zellulare Automaten - Das FSP

    Vortrag: Michael Bauland
    Termin: 09.07.01

  13. Klassifikation zellularer Automaten

    Vortrag: Nils Bertschinger
    Termin: 16.07.01

Literatur

1. D. Drusinsky, D. Harel: On the Power of Bounded Concurrency I: Finite Automata. Journal of the ACM 41:517-539, 1994.
2. J. Kari, C. Moore: New Results on Alternating and Non-Deterministic Two-Dimensional Finite-State Automata. In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, LNCS 2010, pages 396-406, 2001.
3. M. Y. Vardi: An Automata-Theoretic Approach to Linear Temporal Logic. Full Version of the conference paper in Logics for Concurrency: Structure Versus Automata, LNCS 1043, pages 238-266, 1996.
4. F. Somenzi, R. Bloem: Efficient Büchi Automata from LTL formula. In Proceedings of the 12th International Conference on Computer Aided Verification, LNCS 1855, pages 248-263, 2000.
K. Etessami, G.J. Holzmann: Optimizing Büchi Automata. In Proceedings of the 11th International Conference on Concurrency Theory, LNCS 1877, pages 153-167, 2000.
5.-7. O. Kupferman, M.Y. Vardi, P.Wolper: An Automata-Theoretic Approach to Branching- Time Model Checking. Full Version of conference paper in Proceedings of the 6th International Conference on Computer Aided Verification, LNCS 818, pages 142-155,1994.
A. Rabinovich: Symbolic Model Checking for mu-calculus Requires Exponential Time. Submitted for publication.
8. R. Gerth, D. Peled, M.Y. Vardi, P. Wolper: Simple On-the-fly Verification of Linear Temporal Logic. In Son T. Vuong (edt.) Protocol Specification, Testing and Verification XIV, Chapman & Hall, 1995.
9. O.H. Ibarra: Reversal bounded Multicounter Machines and Their Decision Problems. Journal of the ACM 25:116-133, 1978.
E. M. Gurari, O. H. Ibarra: The Complexity of Decision Problems for Finite-Turn Multicounter Machines. Journal of Computer and System Science 22:220-229, 1981.
10. O. H. Ibarra, T. Bultan, J. Su: Reachability Analysis for Some Models of Infinite-State Transition Systems In Proceedings of the 11th International Conference on Concurrency Theory, LNCS 1877, pages 183-198, 2000.
11.-12. Kapitel 20 aus G. Goos: Vorlesungen über Informatik, Band 4, Springer 1998.
Kapitel 2 aus R. Vollmar, T. Worsch: Modelle der Parallelverarbeitung, Teubner, 1995.
13. G. Braga, G. Cattabneo, P. Flocchini, C. Quaranta Vogliotti: Pattern Growth in Elementary Cellular Automata. Theoretical Computer Science 145:1-26, 1995.