Target group
PhD students in computer science, in particular students in the Swedish National Graduate School in Computer Science (CUGS).

Prerequisites
A first course in discrete mathematics including up-to-date knowledge of sets, relations, functions, induction, and basic finite automata theory.

Organisation
Four half-days of lectures (4 hours each day) plus self-studies in the form of home assignments.

Objectives
To provide an understanding of mathematical tools for defining semantics of discrete systems and for analysis and verification of such systems.

Contents
Ordered sets, well-founded orderings, well-orders, ordinals, ordinal powers, inductive definitions, well-founded induction, transfinite induction, lattices, complete lattices, complete partial orders, Knaster-Tarski fixed point theorem, Kleene's fixed point theorem, omega-languages, Büchi and Muller automata.

Litterature
Lecture notes

Examination
Home assignments

Credits
2.5 credits


Page responsible: Ulf Nilsson
Last updated: 2012-05-07