Seminar Algebraische Strukturen als Grundlage der Informatik

Die Vorbesprechung ist am Dienstag, 18.10.2011 ab 16:15 Uhr in O27-429.

Inhalt des Seminars

In der Informatik benötigt man häufig diskrete Strukturen zur Modellierung. Dieses Seminar behandelt algebraisch beschreibbare Strukturen, wie beispielsweise Halbringe, Verbände und Kleene-Algebren. Mögliche Themen aus diesen Bereichen sind:

  • Halbringe: Grundlagen, Polynome, unendliche Summen
  • Verbände: Grundlagen, Fixpunkte, Galois-Verbindungen, μ-Fusion
  • Kleene-Algebren: Grundlagen, reguläre Vollständigkeit, Tests, Omega-Algebren, modale Operatoren

Ausarbeitung und Vortrag

Sie schreiben eine 10-15 Seiten umfassende Ausarbeitung unter Verwendung dieser LaTeX- und BibTeX-Vorlage. Fünf Wochen vor dem Vortrag besprechen Sie den Inhalt der Ausarbeitung mit Ihrem Betreuer. Ihre Literaturrecherche muß bis dann abgeschlossen sein. Zwei Wochen vor dem Vortrag geben Sie die endgültige Fassung Ihrer Ausarbeitung und eine Gliederung des Vortrags ab. Eine Woche vor dem Vortrag haben Sie die letzte Besprechung des Vortrags mit Ihrem Betreuer. Ihr Vortrag dauert 45 Minuten.

Literatur

[1] Aarts, C. J., R. C. Backhouse, E. A. Boiten, H. Doornbos, N. van Gasteren, R. van Geldrop, P. F. Hoogendijk, E. Voermans und J. van der Woude: Fixed-Point Calculus. Information Processing Letters, 53(3):131-136, 10. Februar 1995.
[2] Backhouse, R.: Regular algebra applied to language problems. Journal of Logic and Algebraic Programming, 66(2):71-111, Februar-März 2006.
[3] Cohen, E.: Separation and Reduction. In: Backhouse, R. und J. N. Oliveira (Herausgeber): Mathematics of Program Construction, Band 1837 der Reihe Lecture Notes in Computer Science, Seiten 45-59. Springer-Verlag, 2000.
[4] Conway, J. H.: Regular Algebra and Finite Machines. Chapman and Hall, 1971.
[5] Davey, B. A. und H. A. Priestley: Introduction to Lattices and Order. Cambridge University Press, Second Auflage, 2002.
[6] Desharnais, J., B. Möller und G. Struth: Kleene algebra with domain. ACM Transactions on Computational Logic, 7(4):798-833, Oktober 2006.
[7] Desharnais, J., B. Möller und G. Struth: Algebraic notions of termination. Report 2006-23, Institut für Informatik, Universität Augsburg, Oktober 2006.
[8] Desharnais, J., B. Möller und F. Tchier: Kleene under a modal demonic star. Journal of Logic and Algebraic Programming, 66(2):127-160, Februar-März 2006.
[9] Grätzer, G.: General Lattice Theory. Birkhäuser, 2. Auflage, 1998.
[10] Hebisch, U. und H. J. Weinert: Halbringe. Teubner, 1993.
[11] Kozen, D.: A completeness theorem for Kleene algebras and the algebra of regular events. Information and Computation, 110(2):366-390, Mai 1994.
[12] Kozen, D.: Kleene algebra with tests. ACM Transactions on Programming Languages and Systems, 19(3):427-443, Mai 1997.
[13] Maddux, R. D.: Relation-algebraic semantics. Theoretical Computer Science, 160(1-2):1-85, Juni 1996.
[14] Schmidt, G., C. Hattensperger und M. Winter: Heterogeneous Relation Algebra. In: Brink, C., W. Kahl und G. Schmidt (Herausgeber): Relational Methods in Computer Science, Kapitel 3, Seiten 39-53. Springer-Verlag, Wien, 1997.
[15] Schmidt, G. und T. Ströhlein: Relationen und Graphen. Springer-Verlag, 1989.
[16] Szász, G.: Introduction to Lattice Theory. Academic Press, 3. Auflage, 1963.
[17] Tarski, A.: On the calculus of relations. The Journal of Symbolic Logic, 6(3):73-89, September 1941.
[18] Tarski, A.: A Lattice-Theoretical Fixpoint Theorem and its Applications. Pacific Journal of Mathematics, 5(2):285-309, 1955.

Termin

Dienstag 16-18 Uhr in O27-429