2D5377 Algebras + Coalgebras = Data Types + Systems
Dates: To start week 38.
Classes: 14 tutorials over 14 weeks, Once weekly, 2 * 45 minutes, each Friday 10.15-12.00 during weeks 38 (Friday 18th September) until 51 (Friday 18th December).
Location: School of Computer Science and Communications (CSC) KTH,
KTH Main Campus, Stockholm.
Room 1625 Lindstedtsvägen 3.
Lecturer: Karl Meinke <e-mail me>
Course Weighting: 6 points
Course Assessment: by individual project
This course will repeat the popular course given in 2004 and 2007, with only minor changes. Algebra and category theory have played a central role in the development of programming languages since the 1970s. From among the many contributions to these fields, we can discern two important lines of development:
Underlying these two broad lines of development are two closely related, and often dual theories, universal algebra and universal coalgebra. We take as our course theme the view that algebras and coalgebras model static and dynamic aspects of systems. (Hence the title of our course, though this view is not entirely accurate.) We shall discuss the main features of these theories with reference to some of their computing applications such as initial algebra semantics, term rewriting and Knuth Bendix completion, final coalgebra semantics, bisimulation and coinduction.
The course will focus on two main texts that we will attempt to cover:
1. K. Meinke and J.V. Tucker, Universal Algebra, pp 189-411 in: S. Abramsky, D. Gabbay and T.S.E. Maibaum (eds), Handbook of Logic in Computer Science, Volume 1, Oxford University Press, 1993.
2. J.J.M.M. Rutten, Universal Coalgebra: a Theory of Systems, CWI Report CS-R9652, CWI Amsterdam, 1996.
Course Content (Provisional).
Part I: Algebras
1. Background and Motivation
2. Fundamentals, sets, categories and functors, duality
3. Signatures, and algebras
4. Isomorphisms, homomorphisms, initial, free and final objects
5. Subalgebras, direct products
6. Equations, initial models, equational logic, term rewriting, completion, varieties, Horn clauses, quasivarieties
Part II: Coalgebras
7. Coalgebras and models of systems
8. Limits and colimits
11. Coinductive definition and proof
Page last modified: 2009-09-07