Automata and Learning

This 6-hour tutorial will give an in-depth introduction to provably correct algorithms for learning finite-state automata. We will cover multiple classes of automata (deterministic, probabilistic, and weighted) and different information models and learning guarantees (exact learning, PAC learning, and statistical learning). The goal of the course is to provide a coherent picture where classical results on query learning and recent works on spectral learning fit together. The presentation will stress the trade-offs that arise from different modelling assumptions, and highlight interesting open problems. No prior knowledge on learning theory is required.