Angluin learning via logic

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

2 Citations (Scopus)
99 Downloads (Pure)


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 T-coalgebra 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 languageEnglish
Title of host publicationLogical Foundations of Computer Science
Subtitle of host publicationInternational Symposium, LFCS 2018, Deerfield Beach, FL, USA, January 8–11, 2018, Proceedings
EditorsSergei Artemov, Anil Nerode
Place of PublicationCham
Number of pages19
ISBN (Print)9783319720555
Publication statusPublished - 28 Nov 2017
EventInternational Symposium on Logical Foundations of Computer Science - Deerfield Beach, United States
Duration: 8 Jan 201811 Jan 2018

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


ConferenceInternational Symposium on Logical Foundations of Computer Science
Abbreviated titleLCFS 2018
Country/TerritoryUnited States
CityDeerfield Beach


  • automata learning
  • coalgebra
  • modal logic


Dive into the research topics of 'Angluin learning via logic'. Together they form a unique fingerprint.

Cite this