[Back]

N. Bazhenov, E. Fokina, L. San Mauro:
"Learning families of algebraic structures from informant";
Information and Computation, 275 (2020).

We combine computable structure theory and algorithmic learning theory to study learning of families of algebraic structures. Our main result is a model-theoretic characterization of the class $\Inf\Ex_{\cong}$, consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures is $\Inf\Ex_{\cong}$-learnable if and only if the structures from $\mathfrak{K}$ can be distinguished in terms of their $\Sigma^{\inf}_2$-theories. We apply this characterization to familiar cases and we show the following: there is an infinite learnable family of distributive lattice; no pair of Boolean algebras is learnable; no infinite family of linear orders is learnable.

http://dx.doi.org/10.1016/j.ic.2020.104590