Personal tools
You are here: Home Events LFCS seminar: Clemens Kupke: Learning via Coalgebraic Logic

LFCS seminar: Clemens Kupke: Learning via Coalgebraic Logic

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
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 T-coalgebra 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.

Document Actions