(Co)algebraic foundations for active learning (Alexandra Silva)

Automata models are some of the simplest structures in Computer Science, yet they play a crucial role in verification and semantics. In this talk, I want to explore how different types of automata models, including probabilistic and weighted variants, can be studied in a generic way using (co)algebra. I will illustrate the abstract framework and its use in model learning, a popular verification technique for black-box systems. In particular, I will discuss Dana Angluin's L* learning algorithm, and how more advanced variants of L* for weighted and register automata can be automatically derived. This general framework is an instance of a fundamental duality in Computer Science between algebras and coalgebras, which can be used to develop new algorithms beyond learning for a wide variety of automata. 

Short bio

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 Professor of Algebra, Semantics, and Computation at University College London. Previously, she was an assistant professor in Nijmegen and 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. She was the recipient of the Royal Society Wolfson Award 2019, Needham Award 2018, the Presburger Award 2017, the Leverhulme prize 2016, and an ERC starting Grant in 2015.