On learning down-sets in quasi-orders, and ideals in Boolean algebras.
Saved in:
| Title: | On learning down-sets in quasi-orders, and ideals in Boolean algebras. |
|---|---|
| Authors: | Bazhenov, Nikolay1,2 (AUTHOR) nickbazh@yandex.ru, Mustafa, Manat3 (AUTHOR) manat.mustafa@nu.edu.kz |
| Source: | Theory of Computing Systems. Mar2025, Vol. 69 Issue 1, p1-15. 15p. |
| Subjects: | Ideals (Algebra), Computable functions, Algebra, Mathematics, Boolean algebra, Families |
| Abstract: | 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | 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. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 14324350 |
| DOI: | 10.1007/s00224-024-10201-y |
