Coalgebra for Computer Scientists, Summer semester 2011/2012

E184 Institute of Information Systems, Faculty of Informatics, Vienna University of Technology, Official reference 184.731

Lecturer:      Dr. Ana Sokolova, anas"at"

Schedule:      Thursdays 2:00pm-4:00pm (then 2:30-4:00 pm, with slight adjustments when needed) Seminarraum Goedel. Check the detailed schedule below.

First meeting:    Thursday, 8.3.2011, 2:00pm, Seminarraum Goedel

Language:      English

Course aim and description: The goal is to get acquainted with the theory of coalgebra and its use in computer science. Also, along the way, the students will get to know some category theory notions that are needed for basic constructions and results in coalgebra. The course is meant for computer science students (possibly also some mathematics students) interested in computer science theory. If you are a student interested in formal methods, concurrency theory, and/or automata, and/or you always wondered what is category theory good for, then this may be the right course for you. The teaching consists of lectures interspersed with exercises.

The theory of coalgebra is a relatively recent (20 years old) unifying theory at the abstract end of formal methods. It is a (one could say "the") theory of dynamic systems, of states and observations. Coalgebras allow for a uniform treatment of many different types of automata (e.g. deterministic, nondeterministic, probabilistic, and weighted), their behavior, and their corresponding modal logics. These topics will be covered within the course.

Prerequisites: Basics of theoretical computer science like logic, sets, and automata theory are needed to follow this course. For the rest, the course will be self-contained.

Exam: This is a VU course. There will be an exam at the very end of the semester. The exam is written and it consists of several questions/excersises from the material covered during the course. Additionally, the homework and paper presentation will also contribute to the final grade.
Exam dates: Paper presentations, Monday, July 16, 2012, starting at 2pm, room Manger (see schedule below).
Written exam, Thursday, July 19, 2012, starting at 2pm, Seminarraum Goedel.
Extra meeting for questions and answers before the exam, Tuesday, July 17, 2012, starting at 2pm, Seminarraum Goedel.

Announcements and important news:
Homework and paper assignements: HW week 1: task 1.1.1 from the book; HW week 2: task 1.2.8 from the book; no HW week 3 (more things to read); no HW week 4; HW week 5: task 2.2.5 from the book (and a more involved finality task as a preparation for what comes next); Instead of a HW week 6, please read the paper(s) by Barr ref.[31] in the book. If you have a problem with accessing the paper, send me an email. HW week 7: fill in the missing details of the coalgebraic proof of correctness of Brzozowski's minimization algorithm (Lemma 1 - Lemma 5, formulated in class). HW week 8: prove that for LTS a relation is a coalgebraic bisimulation (Aczel and Mendler) if and only if it is a (concrete) bisimulation (Park). HW week 9: (1) Is bisimilarity an equivalence for the Sets functor that does not preserve weak pullbacks? The functor can be found in the paper by Aczel and Mendler from 1989 or in Example 4.3.7 in my PhD thesis --- download pdf from my webpage, link "papers" scroll down to 2005. (2) Prove that behavioral equivalence on a single coalgebra is indeed an equivalence (without any additional assumptions). HW week 10: Prove that the construction of a coequilizer in Sets provides a coequilizer in CoAlg(F). HW week 11: Prove (directly, without using behavioral equivalence, or find an existing proof) that in the presence of a final coalgebra for a weak pullback preserving functor, bisimilarity and final coalgebra semantics coincide.

Schedule: More detailed information will appear here after each meeting.