Abstract
We propose a generic categorical framework for learning unknown formallanguages of various types (e.g. finite or infinite words, trees, weighted andnominal languages). Our approach is parametric in a monad T that represents thegiven type of languages and their recognizing algebraic structures. Using theconcept of an automata presentation of T-algebras, we demonstrate that the taskof learning a T-recognizable language can be reduced to learning an abstractform of automaton, which is achieved via a generalized version of Angluin's L*algorithm. The algorithm is phrased in terms of categorically describedextension steps; we provide for a generic termination and complexity analysisbased on a dedicated notion of finiteness. Our framework applies to structureslike tree languages or omega-regular languages that were not within the scopeof existing categorical accounts of automata learning. In addition, it yieldsnew generic learning algorithms for several types of languages for which nosuch algorithms were previously known at all, including sorted languages,nominal languages with name binding, and cost functions.