Literatur

Diese Seite wird zur Zeit überarbeitet.
This page is currently under construction.

» Literatur zu den aktuellen Veranstaltungen wird im Handapparat der Bibliothek zur Verfügung gestellt.

Empfohlene Literatur für verschiedene Veranstaltungen.

Angewandte Automatentheorie

  • W. Thomas. Applied Automata Theory. Lecture Notes. RWTH Aachen, 2004.
  • J. Berstel. Transductions and Context-Free Languages. Teubner, 1979.
  • A. Paz. Introduction to Probabilistic Automata. Academic Press, 1971.
  • H. Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, 1994.
  • M. Steinby and W. Thomas. Trees and term rewriting in 1910: On a paper by Axel Thue. Bulletin of the European Association for Theoretical Computer Science, 72:256-269, 2000. [PostScript]
  • O. Matz and A Potthoff. Computing small nondeterministic finite automata. In: Tools and Algorithms for the Construction and Analysis of Systems, Volume NS-95-s of BRICS Notes Series, pages 74-88, 1995. [PostScript]
  • D. Giammarresi, A. Restivo, S. Seibert, and W. Thomas. Monadic second-order logic over rectangular pictures and recognizability by tiling systems. Information and Computation, 125(1):32-45, 1996.

Introductory Books

  • Andre Arnold. Finite Transition Systems. Prentice Hall, 1994.
  • Doron A. Peled. Software Reliability Methods. Springer, 2001.

Books and Articles on Specific Topics

  • Edmund M. Clarke, Orna Grumberg, Doron A. Peled. Model Checking. MIT Press, 1999.
  • Ferenc Gécseg, Magnus Steinby. Tree Languages. In G. Rozenberg, A. Salomaa: Handbook of Formal Language Theory, Vol. 3, Springer, 1997.
  • Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.). Automata, Logics, and Infinite Games. LNCS 2500, Springer, 2002.
  • Fred Kröger. Temporal Logic of Programs. EATCS Monographs on Theoretical Computer Science, 8, Springer, 1987.
  • Zohar Manna, Amir Pnueli. The Temporal Logic of Reactive and Concurrent Systems. Springer, 1992.
  • James L. Peterson. Petri Nets. ACM Computing Surveys (CSUR), Volume 9, Issue 3, September 1977.
  • W. Thomas:
    Boolesche Logik und Büchi-Elgot-Trakhtenbrot-Logik in der Beschreibung diskreter Systeme.
    In P. Horster (Hrsg.), Angewandte Mathematik, insbesondere Informatik, S. 282-300. Vieweg 1999.
    Download unter Publikationen.
  • M. Steinby:
    Tree languages.
    In G. Rozenberg, A. Salomaa (Hrsg.), Hanbook of Formal Language Theory, Bd. 3, Springer 1997.

Automata and Reactive Systems

  • Wolfgang Thomas. Automata and Reactive Systems. Lecture Notes. [ Slides (pdf), Script (pdf, ps.gz) ]
  • W. Thomas. Automata on Infinite Objects. Technical Report, Aachener Informatik-Berichte 88-17, RWTH Aachen, 1988. [ pdf ]
  • W. Thomas. Languages, automata, and logic. Technical Report 9607, Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität zu Kiel, Germany, May 1996. [ ps ]
  • B. Khoussainov and A. Nerode. Automata Theory and Its Applications. Birkhäuser 2001.
  • D. Perrin and J.-E. Pin. Infinite Words. Pure and Applied Mathematics Vol 141, Elsevier, 2004.
  • E. Grädel, W. Thomas and T. Wilke (Eds). Automata, Logics, and Infinite Games. LNCS Vol. 2500, Springer, 2002.

Rekursionstheorie

  • N.J. Cutland. Computability - An Introduction to Recursive Function Theory. Cambridge University Press, Cambridge 1980.
    (empfehlenswerte Einführung in die Thematik)
  • H. Hermes. Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. Springer, 1978.
  • R. Péter. Rekursive Funktionen. Akad. Kiadó, Budapest, 1951.
  • W. Felscher. Berechenbarkeit. Springer, 1993.
  • P. Odifreddi. Classical Recursion Theory. North-Holland, 1989.
  • H. Rogers. Theory of Recursive Functions and Effective Computability. McGraw Hill, New York 1967.
    (DAS Standardwerk zur Rekursionstheorie)
  • A. Yasuhara. Recursive Function Theory and Logic. Academic Press, 1971.
  • W.S. Brainerd and L.H. Landweber. Theory of Computation. Wiley, 1974.
  • J. Barwise (Editor). Handbook of Mathematical Logic. North-Holland, 1977 (Part C).
  • Das Skript zur Vorlesung "Rekursionstheorie" vom SS 2003.

Strukturtheorie regulärer und kontextfreier Sprachen

  • H. Straubing: Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston 1994.
  • J.E. Pin: Varieties for Formal Languages. Plenum Press, New York 1986.
  • J. Berstel: Transductions and Context-Free Languages. Teubner, Stuttgart 1979

Baumautomaten und Anwendungen

Allgemein zu Baumautomaten

  1. E. Grädel, W. Thomas, and Th. Wilke. Automata, logics, and infinite games, volume 2500 of Lecture Notes in Computer Science. Springer, 2002.
  2. W. Thomas. Languages, automata, and logic. Technical Report 9607, Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität zu Kiel, Germany, May 1996. [ PostScript-Datei ]
  3. Das Skript und die Folien zur Vorlesung "Automata and Reactive Systems".

Literatur zu Paritätsspielen

  1. Der in der Vorlesung vorgestellte Algorithmus basiert auf folgendem Artikel (siehe Publikationsseite von Marcin Jurdziński):
    Marcin Jurdziński. Small Progress Measures for Solving Parity Games. In Proceedings of STACS 2000, Volume 1770 of Lecture Notes in Computer Science, Springer, 2000.
  2. Weitere Algorithmen werden in den Kapiteln 6 und 7 des oben genannten Sammelbands Automata, logics, and infinite games vorgestellt.

Literatur zu PDL

Die in 1 und 2 angegebenen Quellen sind allgemeine Artikel zum Thema "dynamische Logik". Dort wird der Zusammenhang zu Baumautomaten nicht behandelt. Der Beweis für die Entscheidbarkeit des Erfüllbarkeitsproblems mit Büchi-Baumautomaten, der in der Vorlesung vorgestellt wird, ist auf dem Artikel 3 aufgebaut. Eingeführt wurde PDL in dem Artikel 4.
  1. D. Kozen und J. Tiuryn. Logics of Programs Kapitel 14 im Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics. Elsevier and MIT Press, 1990.
  2. D. Harel, D. Kozen und J. Tiuryn. Dynamic Logic. MIT Press, 2000
    Eine ältere Version aus dem Handbook of Philosophical Logic als PostScript-Datei
  3. M.Y. Vardi und P. Wolper. Automata-theoretic techniques for modal logics of programs. Journal of Computer and System Sciences, Vol. 32, No.2, pp. 183-221, 1986
    Als PDF Dokument auf der Publikationsseite von M.Y. Vardi
  4. M.J. Fischer und R.E. Ladner. Propositional dyncamic logic of regular programs. Journal of Computer and System Sciences, Vol. 18, No.2, pp. 194-211, 1979

Model-Checking

  • Edmund M. Clarke, Orna Grumberg, Doron A. Peled
    Model checking
    MIT Press, 1999
  • Joost-Pieter Katoen,
    Concepts, algorithms and tools for model checking,
    Erlangen: Institut f. Mathematische Maschinen und Datenverarbeitung, 1999
  • Kenneth L. McMillan,
    Symbolic model checking,
    Kluwer Academic, 1993

Automatentheorie und Formale Sprachen / Formale Systeme, Automaten, Prozesse

Zur Einführung empfehlen wir die drei folgenden Bücher:

  • J.E. Hopcroft, R. Motwani, and J.D. Ullman. Introduction to Automata Theory, Languages and Computation. 2. Aufl., Addison-Wesley, Boston 2001.
  • M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, Boston 1997.
  • Dexter C. Kozen. Automata and Computability. Springer, 1997.

Andere einführende Standardwerke sind:

  • M.D. Davis and E.J. Weyuker. Computability, Complexity and Languages. Academic Press, New York 1983.
  • H.R. Lewis and C. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, N.J. 1981.
  • U. Schöning. Theoretische Informatik - kurzgefaßt. BI-Wissenschaftsverlag, Mannheim 1992.
  • D. Wood. Theory of Computation. Harper & Row, New York 1987.

Zur Ergänzung empfehlen wir die folgende weiterführende Literatur:

  • M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, Reading, Mass. 1978
  • J.E. Hopcroft and J.D. Ullman. Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley, Bonn 1988.

Automaten, Sprachen und Komplexität

  • N. Blum. Theoretische Informatik - Eine anwendungsorientierte Einführung. Oldenbourg, 1998.
  • A.K. Dewdney. Der Turing Omnibus - Eine Reise durch die Informatik mit 66 Stationen. Springer-Verlag, 1995.
  • D. Harel. Algorithmics - The Spirit of Computing. Addison-Wesley, Reading, Mass., 1987.
  • H.R. Lewis, C.H. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, NJ, 1981.
  • J. v. Leeuwen (Ed.): Handbook of Theoretical Computer Science. Vols. A, B, Elsevier, Amsterdam, 1990
  • U. Schöning. Theoretische Informatik - kurzgefasst. Spektrum Akad. Verlag, 3. Auflage, 1997.
  • M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, Boston, 1995.
  • W. Thomas. Automaten, Sprachen, Komplexität. Vorlesungsskript, 2005.
  • G. Vossen, K.-U. Witt. Grundlagen der Theoretischen Informatik mit Anwendungen. Vieweg, 2000.

Berechenbarkeit und Komplexität

  • E. Börger. Berechenbarkeit, Komplexität, Logik. Vieweg, 1985.
    (Reichhaltiges Werk mit vielen Literaturhinweisen)
  • W.S. Brainerd, L.H. Landweber: Theory of Computation. Wiley, 1974.
    Berechenbarkeitstheorie über Wörtern, ausführlich und umfassend.
  • M.R. Garey and D.S. Johnson. Computers and Intractability. Freeman, 1979.
    ("Die Bibel der NP-Vollständigkeit")
  • D. Harel: Algorithmics - The Spirit of Computation. Addison-Wesley, 1987.
    sehr lesenswerte informelle Einführung
  • M.A. Harrison. Agorithmics - The Spirit of Computing. Addison-Wesley, 1987.
  • R. Herken: The Universal Turing Machine: A Half-Century Survey. Springer, 1994.
    weiterführende, auch philosophische Artikel zur Berechnbarkeit
  • J. Hromkovic: Theoretische Informatik. Teubner, 2004.
    gut lesbare Einführung in die Theoretische Informatik
  • H.R. Lewis, C.H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall, 1981.
    gut lesbares Lehrbuch zur Theoretischen Informatik
  • Z. Manna. Mathematical Theory of Computation. McGraw-Hill, New York 1974.
    (Enthält auch Ergebnisse zur Theorie der Programmierung)
  • R. McNaughton. Elementary Computability, Formal Languages and Automata.. Prentice Hall, 1982.
    (Gut motivierende, ausführliche Einführung)
  • C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
  • A. Salomaa. Computation and Automata. Cambridge University Press, 1985.
  • M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, Boston 1997.
  • U. Schöning. Theoretische Informatik - kurzgefaßt. Spektrum, 1997.
  • K.W. Wagner: Theoretische Informatik. Springer, 1994.
    sorgfältige Darstellung der elementaren Berechenbarkeitstheorie
  • D. Wood: Theory of Computation. Harper & Row, 1987.
    ein "Course Book" mit vielen Beispielen

Datenstrukturen und Algorithmen

  • T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, and McGraw-Hill, NY, 1993.
  • K. Mehlhorn. Effiziente Algorithmen. Bde. 1, 2, 3 (primär Bd. 1), Teubner, Stuttgart, 1988.
  • R. Sedgewick. Algorithms. 2nd. ed., Addison-Wesley, Reading, MA, 1988.
  • A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.

Information und Datenschutz

  • R. Mathar. Informationstheorie. Diskrete Modelle und Verfahren. Teubner, 1996.
  • A. Beutelspacher. Kryptologie. Vieweg, 1996.
  • F.L. Bauer. Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. Springer, 1997.
  • R. Kippenhahn. Verschlüsselte Botschaften. Geheimschrift, Enigma und Chipkarte. Rowohlt, 1999.
  • Bundesdatenschutzgesetz. Textausgabe, Datakontext 1996.
  • G.F. Müller and M. Wächter. Der Datenschutzbeauftragte. Beck, 1991.
  • S. Nusser. Sicherheitskonzepte im WWW. Springer, 1997.
  • N. Pohlmann. Firewall-Systeme. Sicherheit für Internetz und Intranet. MITP, 2000.

Informatik-Praktikum für Mathematiker bzw. Technik-Kommuniktaion

  • W. Oberschelp and G. Vossen. Rechneraufbau und Rechnerstrukturen. 6. Auflage, Oldenbourg-Verlag, 1994.

LaTeX

Webserver-Installationen zum Testen

  • Für Linux: XAMPP, LAMP oder separate Installation der entsprechenden Komponenten (Apache, PHP, MySQL)
  • Für Windows: XAMPP oder WAMP

HTML und CSS

PHP

SQL und MySQL

Websprachen: Konzepte und Tools

Einige Links: