Learning families of algebraic structures from informant

Standard

Learning families of algebraic structures from informant. / Bazhenov, Nikolay; Fokina, Ekaterina; San Mauro, Luca.

In: Information and Computation, Vol. 275, 104590, 12.2020.

Research output: Contribution to journal › Article › peer-review

Harvard

Bazhenov, N, Fokina, E & San Mauro, L 2020, 'Learning families of algebraic structures from informant', Information and Computation, vol. 275, 104590. https://doi.org/10.1016/j.ic.2020.104590

APA

Bazhenov, N., Fokina, E., & San Mauro, L. (2020). Learning families of algebraic structures from informant. Information and Computation, 275, [104590]. https://doi.org/10.1016/j.ic.2020.104590

Vancouver

Bazhenov N, Fokina E, San Mauro L. Learning families of algebraic structures from informant. Information and Computation. 2020 Dec;275:104590. Epub 2020 Jun 4. doi: 10.1016/j.ic.2020.104590

Author

Bazhenov, Nikolay ; Fokina, Ekaterina ; San Mauro, Luca. / Learning families of algebraic structures from informant. In: Information and Computation. 2020 ; Vol. 275.

BibTeX

@article{6c491038b79441a1b5189dc5607d5746,

title = "Learning families of algebraic structures from informant",

abstract = "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.",

keywords = "Algorithmic learning, Computable structures, Inductive inference, Infinitary logic, Linear orders, Turing computable embeddings, IDENTIFICATION",

author = "Nikolay Bazhenov and Ekaterina Fokina and {San Mauro}, Luca",

year = "2020",

month = dec,

doi = "10.1016/j.ic.2020.104590",

language = "English",

volume = "275",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Science Inc.",

}

RIS

TY - JOUR

T1 - Learning families of algebraic structures from informant

AU - Bazhenov, Nikolay

AU - Fokina, Ekaterina

AU - San Mauro, Luca

PY - 2020/12

Y1 - 2020/12

N2 - 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.

AB - 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.

KW - Algorithmic learning

KW - Computable structures

KW - Inductive inference

KW - Infinitary logic

KW - Linear orders

KW - Turing computable embeddings

KW - IDENTIFICATION

UR - http://www.scopus.com/inward/record.url?scp=85086104258&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2020.104590

DO - 10.1016/j.ic.2020.104590

M3 - Article

AN - SCOPUS:85086104258

VL - 275

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 104590

ER -

ID: 24471088