Seminar Algebraic structures in computer science

The first meeting is Tuesday 18.10.2011 at 16:15 in O27-429.

Topic of the seminar

Discrete structures are often used for modelling in computer science. This seminar treats algebraically characterised structures such as semirings, lattices and Kleene algebras. Possible topics in these areas are:

  • semirings: foundations, polynomials, infinite sums
  • lattices: foundations, fixpoints, Galois connections, µ-Fusion
  • Kleene algebras: foundations, regular completeness, tests, omega algebras, modal operators

Paper and talk

You must write a paper of 10-15 pages using this LaTeX and BibTeX template. Five weeks before the presentation you have to discuss the contents of the paper with your supervisor. You must have completed your research about the topic by then. Two weeks before your presentation you have to submit the final version of the paper and an outline of your talk. You discuss the latter with your supervisor one week before the presentation is scheduled. You have to give a talk of 45 minutes.

Bibliography

[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.

Schedule

Tuesday 16-18 in O27-429