van Heerdt, G;
Sammartino, M;
Silva, A;
(2020)
Learning automata with side-effects.
In:
Coalgebraic Methods in Computer Science.
(pp. pp. 68-89).
Springer Nature
Preview |
Text
camera-ready-11.pdf - Accepted Version Download (485kB) | Preview |
Abstract
Automata learning has been successfully applied in the verification of hardware and software. The size of the automaton model learned is a bottleneck for scalability, and hence optimizations that enable learning of compact representations are important. This paper exploits monads, both as a mathematical structure and a programming construct, to design and prove correct a wide class of such optimizations. Monads enable the development of a new learning algorithm and correctness proofs, building upon a general framework for automata learning based on category theory. The new algorithm is parametric on a monad, which provides a rich algebraic structure to capture non-determinism and other side-effects. We show that this allows us to uniformly capture existing algorithms, develop new ones, and add optimizations.
| Type: | Proceedings paper |
|---|---|
| Title: | Learning automata with side-effects |
| Event: | 15th IFIP WG 1.3 International Workshop, CMCS 2020, Colocated with ETAPS 2020 |
| ISBN-13: | 9783030572006 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/978-3-030-57201-3_5 |
| Publisher version: | https://doi.org/10.1007/978-3-030-57201-3_5 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| Keywords: | Automata, Learning, Side-effects, Monads, Algebras |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10113536 |
Archive Staff Only
 |
View Item |
