Thesis

Angluin learning: a modal logic approach

Downloadable Content

Download PDF
Creator
Rights statement
Awarding institution
  • University of Strathclyde
Date of award
  • 2026
Thesis identifier
  • T18178
Person Identifier (Local)
  • 201685583
Qualification Level
Qualification Name
Department, School or Faculty
Abstract
  • This thesis develops a framework for coalgebra learning by investigating the intersections between automata theory, the theory of coalgebras, and modal logic. We begin by presenting the L∗ algorithm together with foundational notions of automata theory, coalgebra and modal logic. We then reformulate this algorithm within a coalgebraic setting, showing an interesting link between the classical Angluin algorithm and the concept of filtration in modal logic. By reinterpreting the tests used in L∗ as coalgebraic modal formulas, we provide a version of the algorithm specifically for coalgebras that is parametric in an arbitrary finitary set functor B. This algorithm enables the learning of a finite representation of a given, potentially infinite, regular pointed B-coalgebra. Furthermore, by using a duality framework, we generalise this approach to provide an abstract learning algorithm. This framework uses logical formulas as tests based on a dual adjunction between states and logical theories. The resulting algorithm is stated in categorical terms together with proofs of correctness and termination. Also, we extend this framework to handle computational effects, such as non-determinism and alternation. This is achieved through the introduction of BT-coalgebras and forgetful logics, which allow to abstract away from branching behaviours while maintaining a consistent set of logical formulas whose syntax can describe the behaviour of BT-coalgebras and their B-coalgebra counterparts in the same way. Finally, we study how to combine minimisation and reachability rephrasing what has been presented by Lee and Yannakakis using modal logic notions.
Advisor / supervisor
  • Kupke, C. (Clemens)
Resource Type
DOI

Relations

Items

Thumbnail Title Date Uploaded Visibility Actions
file details PDF of thesis T18178 2026-09-30 Public Download