Аннотация
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 learning type InfEx≅, consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures is InfEx≅-learnable if and only if the structures can be distinguished in terms of their Σ2inf-theories. We apply this characterization to familiar cases and we show the following: there is an infinite learnable family of distributive lattices; no pair of Boolean algebras is learnable; no infinite family of linear orders is learnable.
Язык оригинала | английский |
---|---|
Номер статьи | 104590 |
Число страниц | 17 |
Журнал | Information and Computation |
Том | 275 |
Ранняя дата в режиме онлайн | 4 июн 2020 |
DOI | |
Состояние | Опубликовано - дек 2020 |