Classifying different criteria for learning algebraic structures | Sciact - Система учета научной деятельности ИМ СО РАН

Classifying different criteria for learning algebraic structures Научная публикация

Журнал

Annals of Pure and Applied Logic
ISSN: 0168-0072

Вых. Данные

Год: 2026, Том: 177, Номер: 1, Страницы: 103648 Страниц : 25 DOI: 10.1016/j.apal.2025.103648

Ключевые слова

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

Авторы

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

Организации

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

Информация о финансировании (1)

Российский научный фонд

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

Поступила в редакцию:	18 сент. 2024 г.
Принята к публикации:	18 авг. 2025 г.
Опубликована online:	22 авг. 2025 г.
Опубликована в печати:	27 авг. 2025 г.

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

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