Abstract
| 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 | |
| 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
Cite this
}
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
ER -