Elements of Kleene Algebra

About

You have most likely been exposed to a fair amount of equational reasoning, whether it was used to apply Newtons laws or to manipulate polynomials. But the principles behind this approach are not limited to numbers: this course provides an introduction to Kleene Algebra, an equational approach to specify and reason about sequences of events with applications ranging from pattern matching to program verification using propositional Hoare logic.
The material covered will focus primarily on the logical and computational aspects of Kleene Algebra. We will cover Kozens completeness theorem, which says that any true equivalence of regular expressions can be proved, as well as its intricate connection to Kleenes theorem, which relates regular expressions to finite automata. Along the way, we will encounter some elegant mathematical constructions, such as Brzozowskis derivatives, as well as useful extensions of the core calculus, including Kleene Algebra with Tests.

Course leader

Tobias Kappé

Target group

Students

Fee info