On learning down-sets in quasi-orders, and ideals in Boolean algebras

Bazhenov N. Mustafa M.
March 2025 Springer

Theory of Computing Systems
2025 #69 Issue 1

The paper studies learnability from positive data for families of down-sets in quasi-orders, 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 down-sets 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.

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

Text of the article Перейти на текст статьи

Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., Novosibirsk, 630090, Russian Federation
Kazakh-British Technical University, 59 Tole Bi Street, Almaty, 050000, Kazakhstan
Department of Mathematics, School of Sciences and Humanities, Nazarbayev University, 53 Qabanbaybatyr Avenue, Astana, 010000, Kazakhstan

Sobolev Institute of Mathematics
Kazakh-British Technical University
Department of Mathematics

10 лет помогаем публиковать статьи Международный издатель

Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026