Projects per year
Abstract
In this paper we will provide a fresh take on Dana Angluin's algorithm for learning using ideas from coalgebraic modal logic. Our work opens up possibilities for applications of tools & techniques from modal logic to automata learning and vice versa. As main technical result we obtain 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 (i.e. having an equivalent finite representation) we can learn its finite representation by asking (i) "logical queries" (corresponding to membership queries) and (ii) making conjectures to which the teacher has to reply with a counterexample. This covers (a known variant) of the original L* algorithm and the learning of Mealy/Moore machines. Other examples are bisimulation quotients of (probabilistic) transition systems.
Original language  English 

Title of host publication  Logical Foundations of Computer Science 
Subtitle of host publication  International Symposium, LFCS 2018, Deerfield Beach, FL, USA, January 8–11, 2018, Proceedings 
Editors  Sergei Artemov, Anil Nerode 
Place of Publication  Cham 
Publisher  Springer 
Pages  7290 
Number of pages  19 
ISBN (Print)  9783319720555 
DOIs  
Publication status  Published  28 Nov 2017 
Event  International Symposium on Logical Foundations of Computer Science  Deerfield Beach, United States Duration: 8 Jan 2018 → 11 Jan 2018 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  10703 
ISSN (Print)  03029743 
Conference
Conference  International Symposium on Logical Foundations of Computer Science 

Abbreviated title  LCFS 2018 
Country  United States 
City  Deerfield Beach 
Period  8/01/18 → 11/01/18 
Keywords
 automata learning
 coalgebra
 modal logic
Profiles
Projects
 1 Finished

Coalgebraic Foundations of SemiStructured Data (EPSRC First Grant)
EPSRC (Engineering and Physical Sciences Research Council)
1/02/16 → 31/01/18
Project: Research