Colloquium Computer Science - Dr. Clemens Kupke (University of Strathclyde, Glasgow)

Title: 

Angluin Learning via Logic

Abstract: 

A key result in computational learning theory is Dana Angluin's L* algorithm that describes how to learn a deterministic finite automaton (DFA) using membership and equivalence queries. I will explain how modal logics can be used to understand its working and to generalise the algorithm to other types of structures, e.g., labelled transition systems (LTSs), using formulas as tests. Our perspective also allows to link the L* algorithm with the Lee/Yannakakis algorithm, an algorithm for quotienting LTSs that intertwines reachability checking and minimisation.