On learning down-sets in quasi-orders, and ideals in Boolean algebras Full article
| Journal |
Theory of Computing Systems
ISSN: 1432-4350 , E-ISSN: 1433-0490 |
||||||
|---|---|---|---|---|---|---|---|
| Output data | Year: 2025, Volume: 69, Number: 1, Article number : 1, Pages count : 15 DOI: 10.1007/s00224-024-10201-y | ||||||
| Tags | Algorithmic learning theory · Computable structure · Quasi-order · Boolean algebra · Ideal · Inductive inference | ||||||
| Authors |
|
||||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0011 |
Abstract:
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.
Cite:
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
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
Dates:
| Submitted: | Nov 21, 2024 |
| Accepted: | Nov 27, 2024 |
| Published online: | Dec 27, 2024 |
| Published print: | Mar 15, 2025 |
Identifiers:
| Web of science: | WOS:001386529000001 |
| Scopus: | 2-s2.0-85213547659 |
| Elibrary: | 80162916 |
| OpenAlex: | W4405823637 |
Citing:
Пока нет цитирований