LFCS seminar: Clemens Kupke: Learning via Coalgebraic Logic
What 


When 
May 30, 2017 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
A key result in computational learning theory is Dana Angluinâ€™s L* algorithm that describes how to learn a regular language, or a deterministic finite automaton (DFA), using membership and equivalence queries. In my talk I will present a generalisation of this algorithm using ideas from coalgebra and modal logic  please note, however, that prior knowledge of these topics will not be required.
In the first part of my talk I will recall how the L* algorithm works and establish a link to the notion of a filtration from modal logic. Furthermore I will provide a brief introduction to coalgebraic modal logic. In the second part of my talk I will present a generalisation of Angluin's original algorithm from DFAs to coalgebras for an arbitrary finitary set functor T in the following sense: given a (possibly infinite) pointed Tcoalgebra that we assume to be regular (ie. having an equivalent finite representation) we can learn its finite representation by (i) asking ``logical queries'' (corresponding to membership queries) and (ii) making conjectures to which a teacher has to reply with a counterexample (equivalence queries). This covers (known variants of) the original L* algorithm and algorithms for learning Mealy and Moore machines. Other examples are infinite streams, trees and bisimulation quotients of various types of transition systems.
Joint work with Simone Barlocco.