View in EDS HTML Full Text PDF Full Text

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

Saved in:
Bibliographic Details
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.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 181927433
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On learning down-sets in quasi-orders, and ideals in Boolean algebras.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Bazhenov%2C+Nikolay%22">Bazhenov, Nikolay</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> nickbazh@yandex.ru</i><br /><searchLink fieldCode="AR" term="%22Mustafa%2C+Manat%22">Mustafa, Manat</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> manat.mustafa@nu.edu.kz</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Theory+of+Computing+Systems%22">Theory of Computing Systems</searchLink>. Mar2025, Vol. 69 Issue 1, p1-15. 15p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Ideals+%28Algebra%29%22">Ideals (Algebra)</searchLink><br /><searchLink fieldCode="DE" term="%22Computable+functions%22">Computable functions</searchLink><br /><searchLink fieldCode="DE" term="%22Algebra%22">Algebra</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematics%22">Mathematics</searchLink><br /><searchLink fieldCode="DE" term="%22Boolean+algebra%22">Boolean algebra</searchLink><br /><searchLink fieldCode="DE" term="%22Families%22">Families</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=181927433
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00224-024-10201-y
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 15
        StartPage: 1
    Subjects:
      – SubjectFull: Ideals (Algebra)
        Type: general
      – SubjectFull: Computable functions
        Type: general
      – SubjectFull: Algebra
        Type: general
      – SubjectFull: Mathematics
        Type: general
      – SubjectFull: Boolean algebra
        Type: general
      – SubjectFull: Families
        Type: general
    Titles:
      – TitleFull: On learning down-sets in quasi-orders, and ideals in Boolean algebras.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Bazhenov, Nikolay
      – PersonEntity:
          Name:
            NameFull: Mustafa, Manat
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 03
              Text: Mar2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 14324350
          Numbering:
            – Type: volume
              Value: 69
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: Theory of Computing Systems
              Type: main
ResultId 1