TY - GEN

T1 - On Learning Families of Ideals in Lattices and Boolean Algebras

AU - Bazhenov, Nikolay

AU - Mustafa, Manat

N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.

PY - 2024

Y1 - 2024

N2 - The paper studies learnability from positive data for families of ideals in lattices and Boolean algebras. We established some connections between learnability and algebraic properties of the underlying structures. We prove that for a computable lattice L, the family of all its ideals is BC-learnable (i.e., learnable w.r.t. semantical convergence) if and only if each ideal of L is principal. In addition, BC-learnability for the family of all ideals is equivalent to Ex-learnability (learnability w.r.t. syntactic convergence). In general, learnability depends on the choice of a computable isomorphic copy of L. Indeed, 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. Finally, we obtain a reverse-mathematical result about conservative Ex-learning for ideals.

AB - The paper studies learnability from positive data for families of ideals in lattices and Boolean algebras. We established some connections between learnability and algebraic properties of the underlying structures. We prove that for a computable lattice L, the family of all its ideals is BC-learnable (i.e., learnable w.r.t. semantical convergence) if and only if each ideal of L is principal. In addition, BC-learnability for the family of all ideals is equivalent to Ex-learnability (learnability w.r.t. syntactic convergence). In general, learnability depends on the choice of a computable isomorphic copy of L. Indeed, 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. Finally, we obtain a reverse-mathematical result about conservative Ex-learning for ideals.

KW - Algorithmic learning theory

KW - Boolean algebra

KW - Computable structure

KW - Ideal

KW - Inductive inference

KW - Lattice

KW - Linear order

UR - http://www.scopus.com/inward/record.url?scp=85193275144&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85193275144&partnerID=8YFLogxK

U2 - 10.1007/978-981-97-2340-9_1

DO - 10.1007/978-981-97-2340-9_1

M3 - Conference contribution

AN - SCOPUS:85193275144

SN - 9789819723393

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 13

BT - Theory and Applications of Models of Computation - 18th Annual Conference, TAMC 2024, Proceedings

A2 - Chen, Xujin

A2 - Li, Bo

PB - Springer Science and Business Media Deutschland GmbH

T2 - 18th Annual Conference on Theory and Applications of Models of Computation, TAMC 2024

Y2 - 13 May 2024 through 15 May 2024

ER -