Angluin learning via logic

Barlocco, Simone and Kupke, Clemens; Artemov, Sergei and Nerode, Anil, eds. (2017) Angluin learning via logic. In: Logical Foundations of Computer Science. Lecture Notes in Computer Science . Springer, USA, pp. 72-90. ISBN 9783319720555

[thumbnail of Barlocco-Kupke-LFCS2018-Angluin-learning-via-logic]
Preview
 Text (Barlocco-Kupke-LFCS2018-Angluin-learning-via-logic)
Barlocco_Kupke_LFCS2018_Angluin_learning_via_logic.pdf
Accepted Author Manuscript
Download (405kB)| Preview

    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 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.

    • Item type:Book Section
      ID code:63273
      Dates:
      Date
      Event
      28 November 2017
      Published
      10 October 2017
      Accepted
      Notes:This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: https://doi.org/10.1007/978-3-319-72056-2_5
      Keywords:automata learning, coalgebra, modal logic, Electronic computers. Computer science, Computer Science(all)
      Subjects:Science > Mathematics > Electronic computers. Computer science
      Department:Faculty of Science > Computer and Information Sciences
      Depositing user: Pure Administrator
      Date deposited:13 Feb 2018 15:38
      Last modified:05 Apr 2021 00:50
      Related URLs:
      URI:https://strathprints.strath.ac.uk/id/eprint/63273
    CORE (COnnecting REpositories)