UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Learning automata with side-effects

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 Green open access

[thumbnail of camera-ready-11.pdf]
camera-ready-11.pdf - Accepted Version

Download (485kB) | Preview


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
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item