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

A Categorical Framework for Learning Generalised Tree Automata

Heerdt, GV; Kappé, T; Rot, J; Sammartino, M; Silva, A; (2022) A Categorical Framework for Learning Generalised Tree Automata. In: Coalgebraic Methods in Computer Science. (pp. pp. 67-87). Springer Nature: Cham, Switzerland. Green open access

[thumbnail of 2001.05786v1.pdf]
Preview
Text
2001.05786v1.pdf - Accepted Version

Download (410kB) | Preview

Abstract

Automata learning is a popular technique used to automatically construct an automaton model from queries. Much research went into devising ad hoc adaptations of algorithms for different types of automata. The CALF project seeks to unify these using category theory in order to ease correctness proofs and guide the design of new algorithms. In this paper, we extend CALF to cover learning of algebraic structures that may not have a coalgebraic presentation. Furthermore, we provide a detailed algorithmic account of an abstract version of the popular \mathtt {L}^{star} algorithm, which was missing from CALF. We instantiate the abstract theory to a large class of \mathbf {Set} functors, by which we recover for the first time practical tree automata learning algorithms from an abstract framework and at the same time obtain new algorithms to learn algebras of quotiented polynomial functors.

Type: Proceedings paper
Title: A Categorical Framework for Learning Generalised Tree Automata
Event: 16th IFIP WG 1.3 International Workshop, CMCS 2022, Colocated with ETAPS 2022
ISBN-13: 978-3-031-10735-1
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/978-3-031-10736-8_4
Publisher version: https://doi.org/10.1007/978-3-031-10736-8_4
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.
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/10117574
Downloads since deposit
4Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item