Heerdt, GV;
Sammartino, M;
Silva, A;
(2019)
Optimizing Automata Learning via Monads.
arXiv
Preview |
Text
1704.08055v4.pdf - Accepted Version Download (1MB) | 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, prove correct, and implement a wide class of such optimizations. The former perspective on monads allows us to develop a new algorithm and accompanying 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 our approach allows us to uniformly capture existing algorithms, develop new ones, and add optimizations. The latter perspective allows us to effortlessly translate the theory into practice: we provide a Haskell library implementing our general framework, and we show experimental results for two specific instances: non-deterministic and weighted automata.
| Type: | Article |
|---|---|
| Title: | Optimizing Automata Learning via Monads |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | http://arxiv.org/abs/1704.08055v4 |
| Language: | English |
| Additional information: | This is an open access paper distributed under the terms of the Creative Commons Attribution 4.0 International License. |
| 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/10117573 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
