{
  "id": "1905.01601",
  "version": "v1",
  "published": "2019-05-05T04:25:03.000Z",
  "updated": "2019-05-05T04:25:03.000Z",
  "title": "Learning families of algebraic structures from informant",
  "authors": [
    "Nikolay Bazhenov",
    "Ekaterina Fokina",
    "Luca San Mauro"
  ],
  "comment": "22 pages, 1 figure",
  "categories": [
    "math.LO"
  ],
  "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 class $\\mathbf{InfEx}_{\\cong}$, consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures $\\mathfrak{K}$ is $\\mathbf{InfEx}_{\\cong}$-learnable if and only if the structures from $\\mathfrak{K}$ can be distinguished in terms of their $\\Sigma^{\\mathrm{inf}}_2$-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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-05-05T04:25:03.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68Q32",
      "03C57"
    ],
    "keywords": [
      "algebraic structures",
      "learning families",
      "algorithmic learning theory",
      "main result",
      "linear orders"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}