Angluin learning via logic

Simone Barlocco; Clemens Kupke

doi:10.1007/978-3-319-72056-2_5

Angluin learning via logic

Simone Barlocco, Clemens Kupke

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

2 Citations (Scopus)

39 Downloads (Pure)

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.

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	72-90
Number of pages	19
ISBN (Print)	9783319720555
DOIs	https://doi.org/10.1007/978-3-319-72056-2_5
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)	0302-9743

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

Access to Document

10.1007/978-3-319-72056-2_5

Barlocco-Kupke-LFCS2018-Angluin-learning-via-logicAccepted author manuscript, 396 KB

http://lfcs.ws.gc.cuny.edu/lfcs-2018/

Profiles

Clemens Kupke

clemens.kupke@strath.ac.uk

Computer And Information Sciences - Lecturer B
SICSA

Person: Academic

Projects

1 Finished

Coalgebraic Foundations of Semi-Structured Data (EPSRC First Grant)

Kupke, C.

EPSRC (Engineering and Physical Sciences Research Council)

1/02/16 → 31/01/18

Project: Research

Cite this

Barlocco, S., & Kupke, C. (2017). Angluin learning via logic. In S. Artemov, & A. Nerode (Eds.), Logical Foundations of Computer Science: International Symposium, LFCS 2018, Deerfield Beach, FL, USA, January 8–11, 2018, Proceedings (pp. 72-90). (Lecture Notes in Computer Science; Vol. 10703). Springer. https://doi.org/10.1007/978-3-319-72056-2_5

@inproceedings{fa83c4cfa65c4fe4b326df157cf76282,

title = "Angluin learning via logic",

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

keywords = "automata learning, coalgebra, modal logic",

author = "Simone Barlocco and Clemens Kupke",

note = "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; International Symposium on Logical Foundations of Computer Science, LCFS 2018 ; Conference date: 08-01-2018 Through 11-01-2018",

year = "2017",

month = nov,

day = "28",

doi = "10.1007/978-3-319-72056-2_5",

language = "English",

isbn = "9783319720555",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "72--90",

editor = "Sergei Artemov and Anil Nerode",

booktitle = "Logical Foundations of Computer Science",

}

Barlocco, S & Kupke, C 2017, Angluin learning via logic. in S Artemov & A Nerode (eds), Logical Foundations of Computer Science: International Symposium, LFCS 2018, Deerfield Beach, FL, USA, January 8–11, 2018, Proceedings. Lecture Notes in Computer Science, vol. 10703, Springer, Cham, pp. 72-90, International Symposium on Logical Foundations of Computer Science, Deerfield Beach, United States, 8/01/18. https://doi.org/10.1007/978-3-319-72056-2_5

Angluin learning via logic. / Barlocco, Simone ; Kupke, Clemens.

Logical Foundations of Computer Science: International Symposium, LFCS 2018, Deerfield Beach, FL, USA, January 8–11, 2018, Proceedings. ed. / Sergei Artemov; Anil Nerode. Cham : Springer, 2017. p. 72-90 (Lecture Notes in Computer Science; Vol. 10703).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

TY - GEN

T1 - Angluin learning via logic

AU - Barlocco, Simone

AU - Kupke, Clemens

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

PY - 2017/11/28

Y1 - 2017/11/28

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

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

KW - automata learning

KW - coalgebra

KW - modal logic

UR - http://lfcs.ws.gc.cuny.edu/lfcs-2018/

U2 - 10.1007/978-3-319-72056-2_5

DO - 10.1007/978-3-319-72056-2_5

M3 - Conference contribution book

SN - 9783319720555

T3 - Lecture Notes in Computer Science

SP - 72

EP - 90

BT - Logical Foundations of Computer Science

A2 - Artemov, Sergei

A2 - Nerode, Anil

PB - Springer

CY - Cham

T2 - International Symposium on Logical Foundations of Computer Science

Y2 - 8 January 2018 through 11 January 2018

ER -