Learning families of algebraic structures from informant

Nikolay Bazhenov, Ekaterina Fokina, Luca San Mauro

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование


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
ЖурналInformation and Computation
Ранняя дата в режиме онлайн4 июн 2020
СостояниеЭлектронная публикация перед печатью - 4 июн 2020

Fingerprint Подробные сведения о темах исследования «Learning families of algebraic structures from informant». Вместе они формируют уникальный семантический отпечаток (fingerprint).