Classifying different criteria for learning algebraic structures

Classifying different criteria for learning algebraic structures Full article

Journal

Annals of Pure and Applied Logic
ISSN: 0168-0072

Output data

Year: 2026, Volume: 177, Number: 1, Pages: 103648 Pages count : 25 DOI: 10.1016/j.apal.2025.103648

Tags

Inductive inference, Algorithmic learning theory, Infinitary logic, Continuous reducibility

Authors

Bazhenov Nikolay ^1,2 , Cipriani Vittorio ³ , Jain Sanjay ⁴ , San Mauro Luca ⁵ , Stephan Frank ^4,6

Affiliations

1	Sobolev Institute of Mathematics
2	Kazan Federal University
3	Institute of Discrete Mathematics and Geometry, Technische Universität Wien
4	School of Computing, National University of Singapore
5	Department of Philosophy, University of Bari
6	Department of Mathematics, National University of Singapore

Funding (1)

Russian Science Foundation

24-11-00227

In the last years there has been a growing interest in the study of learning problems associated with algebraic structures. The framework we use models the scenario in which a learner is given larger and larger fragments of a structure from a given target family and is required to output an hypothesis about the structure’s isomorphism type. So far researchers focused on Ex-learning, in which the learner is asked to eventually stabilize to the correct hypothesis, and on restrictions where the learner is allowed to change the hypothesis a fixed number of times. Yet, other learning paradigms coming from classical algorithmic learning theory remained unexplored. We study the "learning power'' of such criteria, comparing them via descriptive-settheoretic tools thanks to the novel notion of E-learnability. The main outcome of this paper is that such criteria admit natural syntactic characterizations in terms of infinitary formulas analogous to the one given for Ex-learning in [8]. Such characterizations give a powerful method to understand whether a family of structures is learnable with respect to the desired criterion.

Bazhenov N. , Cipriani V. , Jain S. , San Mauro L. , Stephan F.
Classifying different criteria for learning algebraic structures
Annals of Pure and Applied Logic. 2026. V.177. N1. P.103648. DOI: 10.1016/j.apal.2025.103648 WOS Scopus OpenAlex

Submitted:	Sep 18, 2024
Accepted:	Aug 18, 2025
Published online:	Aug 22, 2025
Published print:	Aug 27, 2025

Web of science:	WOS:001562374100001
Scopus:	2-s2.0-105014651632
OpenAlex:	W4413427393

Пока нет цитирований