11 August 2023
Elements of Kleene Algebra
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
EUR 490: Early student registration
EUR 690: Early non-academic registration
Scholarships
There are several scholarship options which you can read about on our website.