On learning down-sets in quasi-orders, and ideals in Boolean algebras | Sciact - Система учета научной деятельности ИМ СО РАН

On learning down-sets in quasi-orders, and ideals in Boolean algebras Научная публикация

Журнал

Theory of Computing Systems
ISSN: 1432-4350 , E-ISSN: 1433-0490

Вых. Данные

Год: 2025, Том: 69, Номер: 1, Номер статьи : 1, Страниц : 15 DOI: 10.1007/s00224-024-10201-y

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

Algorithmic learning theory · Computable structure · Quasi-order · Boolean algebra · Ideal · Inductive inference

Авторы

Bazhenov Nikolay ^1,2 , Mustafa Manat ³

Организации

1	Sobolev Institute of Mathematics
2	Kazakh-British Technical University
3	Department of Mathematics, School of Sciences and Humanities, Nazarbayev University

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

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0011

The paper studies learnability from positive data for families of down-sets in quasiorders, and for families of ideals in Boolean algebras. We establish some connections between learnability and algebraic properties of the underlying structures. We prove that for a computably enumerable quasi-order (Q,≤Q), the family of all its downsets is BC-learnable (i.e., learnable w.r.t. semantical convergence) if and only if the reverse ordering (Q,≥Q) is a well-quasi-order. In addition, if the quasi-order(Q,≤Q) is computable, then BC-learnability for the family of all down-sets is equivalent to Ex-learnability (learnability w.r.t. syntactic convergence). We prove that for a computable upper semilattice U, the family of all its ideals is BC-learnable if and only if this family is Ex-learnable, if and only if each ideal of U is principal. In general, learnability depends on the choice of an isomorphic copy of U. We show that for every infinite, computable atomic Boolean algebra B, there exist computable algebras A and C isomorphic to B such that the family of all computably enumerable ideals in A is BC-learnable, while the family of all computably enumerable ideals in C is not BC-learnable.

Bazhenov N. , Mustafa M.
On learning down-sets in quasi-orders, and ideals in Boolean algebras
Theory of Computing Systems. 2025. V.69. N1. 1 :1-15. DOI: 10.1007/s00224-024-10201-y WOS Scopus РИНЦ OpenAlex

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

Web of science:	WOS:001386529000001
Scopus:	2-s2.0-85213547659
РИНЦ:	80162916
OpenAlex:	W4405823637

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