The DOI matches its Crossref record.
Learning families of algebraic structures from informant
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“we present a fundamental result that hallucination is inevitable for any computable LLM, regardless of model architecture, learning algorithms, prompting techniques, or training data.”
From Hallucination is Inevitable: An Innate Limitation of Large Language Models (2024) · cites this paper as [4]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Still being checked.
Research works printed but not linked: 20
- Gold, 1967, Language identification in the limit, Inf. Control, 10, 447, 10.1016/S0019-9958(67)91165-5 · DOI · Paper page
- Zeugmann, 2008, Learning recursive functions: a survey, Theor. Comput. Sci., 397, 4, 10.1016/j.tcs.2008.02.021 · DOI
- Lange, 2008, Learning indexed families of recursive languages from positive data: a survey, Theor. Comput. Sci., 397, 194, 10.1016/j.tcs.2008.02.030 · DOI
- Glymour, 1985, Inductive inference in the limit, Erkenntnis, 22, 23, 10.1007/BF00269958 · DOI
- Harizanov, 2007, On the learnability of vector spaces, J. Comput. Syst. Sci., 73, 109, 10.1016/j.jcss.2006.09.001 · DOI
- Merkle, 2004, Trees and learning, J. Comput. Syst. Sci., 68, 134, 10.1016/j.jcss.2003.08.001 · DOI
- Stephan, 2001, Learning algebraic structures from text, Theor. Comput. Sci., 268, 221, 10.1016/S0304-3975(00)00272-3 · DOI
- Fokina, 2019, Limit learning equivalence structures, vol. 98, 383
- Soare, 2016, 10.1007/978-3-642-31933-4 · DOI
- Ash, 2000, Computable Structures and the Hyperarithmetical Hierarchy, vol. 144
- Case, 1983, Comparison of identification criteria for machine inductive inference, Theor. Comput. Sci., 25, 193, 10.1016/0304-3975(83)90061-0 · DOI
- Jain, 2011, Hypothesis spaces for learning, Inf. Comput., 209, 513, 10.1016/j.ic.2010.11.016 · DOI
- Goncharov, 2002, Computable structure and non-structure theorems, Algebra Log., 41, 351, 10.1023/A:1021758312697 · DOI
- Friedberg, 1958, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symb. Log., 23, 309, 10.2307/2964290 · DOI
- Blum, 1975, Toward a mathematical theory of inductive inference, Inf. Control, 28, 125, 10.1016/S0019-9958(75)90261-2 · DOI · Paper page
- Knight, 2007, Turing computable embeddings, J. Symb. Log., 72, 901, 10.2178/jsl/1191333847 · DOI
- Calvert, 2004, Comparing classes of finite structures, Algebra Log., 43, 374, 10.1023/B:ALLO.0000048827.30718.2c · DOI
- Selivanov, 1988, Algorithmic complexity of algebraic systems, Math. Notes, 44, 944, 10.1007/BF01158034 · DOI
- Alaev, 2004, Computable homogeneous Boolean algebras and a metatheorem, Algebra Log., 43, 73, 10.1023/B:ALLO.0000020844.03135.a6 · DOI
- Montalbán, 2010, Counting the back-and-forth types, J. Log. Comput., 22, 857, 10.1093/logcom/exq048 · DOI
Cited by
Hallucination is Inevitable: An Innate Limitation of Large Language Models
Xu, Z., Jain, S., & Kankanhalli, M. (2024) · arXiv · doi:10.48550/arxiv.2401.11817 · Cited by 180
“…of this paper is summarized as follows: • We formally define and discuss hallucination for LLMs and, by employing results in learning theory [2, 3, 18, 28], we show that hallucination is inevitable for LLMs. • Empirical study shows that state-of-the-art LLMs are hallucination-prone in some…”
Background
Metadata
- Authors
- Bazhenov, N., Fokina, E., & San Mauro, L.
- Affiliations
- Novosibirsk State University (RU)
- TU Wien (AT)
- Venue
- Information and Computation
- Publisher
- Elsevier BV
- Published
- 2020-12
- Volume
- 275
- Pages
- 104590
- ISSN
- 0890-5401 (ISSN-L)
- OpenAlex
- W2943260620
- Cited by
- 14
- References
- 0
- Citations by year
- 2025: 4 · 2024: 4 · 2023: 1 · 2022: 2 · 2021: 2 · 2020: 1
- FWCI
- 0.75
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- www.elsevier.com/tdm/userlicense/1.0/ (tdm)
- www.elsevier.com/legal/tdmrep-license (tdm)
- www.elsevier.com/open-access/userlicense/1.0/ (vor, 1461 d)
- doi.org/10.15223/policy-017 (stm-asf)
- doi.org/10.15223/policy-037 (stm-asf)
- doi.org/10.15223/policy-012 (stm-asf)
- doi.org/10.15223/policy-029 (stm-asf)
- doi.org/10.15223/policy-004 (stm-asf)
- Locations
- Information and Computation (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CINECA IRIS Institutional Research Information System (University of Bari Aldo Moro) (submittedVersion)
- Use Siena air (University of Siena) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Russian Science Foundation
- Austrian Science Fund
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Mathematics › Geometry and Topology › Advanced Topology and Set Theory
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Keywords
- computable structure theory, algorithmic learning theory, learning in the limit, isomorphism types, model-theoretic characterization, distributive lattices, Boolean algebra, linear orders, learnability
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Learning families of algebraic structures from informant. https://app.cochat.ai/papers/10.1016/j.ic.2020.104590
- The paper
- Bazhenov, N., Fokina, E., & San Mauro, L. (2020). Learning families of algebraic structures from informant. Information and Computation. https://doi.org/10.1016/j.ic.2020.104590
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
