2017/2018 Edition

Extensions of Kleene Algebra and applications to programming semantics and networks

Lecturer: Alexandra Silva (University College London).

About the lecturer | Course Summary | Slides: 1 2 3 4 | Assignment

About the lecturer: Alexandra Silva is a theoretical computer scientist whose main research focuses on semantics of programming languages and modular development of algorithms for computational models. A lot of her work uses the unifying perspective offered by coalgebra, a mathematical framework established in the last decades.

Alexandra is currently a Senior Lecturer at University College London. Previously, she was an assistant professor at the Radboud University Nijmegen, The Netherlands. Before that, she was a post-doc at Cornell University, with Prof. Dexter Kozen, and a PhD student at the Dutch national research center for Mathematics and Computer Science (CWI), under the supervision of Prof. Jan Rutten and Dr. Marcello Bonsangue.

Course summary: Regular expressions (and languages) are one of the most basic structures in Computer Science and have been object of extensive study since they were proposed by Kleene in the 50's. We will review some basic definitions of regular languages and expressions, including recent algorithmic improvements on deciding equivalence of regular languages. We will then show how simple extensions of regular expressions can widen their applicability to study the semantics of imperative programs and software-defined networks.


Assignment: You can find the problem set here. Please send the solutions to Bartek Klin (klin@you-know-what) by Monday, January 4.