Learning Weighted Automata over Principal Ideal Domains

Learning Weighted Automata over Principal Ideal Domains (via Zoom)

Abstract: In the first part of this talk, we discuss active learning algorithms for weighted automata over a semiring. We show that a variant of Angluin's seminal L* algorithm works when the semiring is a principal ideal domain, but not for general semirings such as the natural numbers. In the second part, we present some preliminary work on active learning for probabilistic automata, and in particular discuss what the setup of the problem looks like and how that leads (or not) to impossibility results. 

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 at Cornell University, and she was previously a Professor at University College London. She was the recipient of an ERC Consolidator in 2020, the Royal Society Wolfson Award 2019, Needham Award 2018, the Presburger Award 2017, the Leverhulme prize 2016, and an ERC starting Grant in 2015.