View in EDS HTML Full Text PDF Full Text

Computably enumerable equivalence relations via primitive recursive reductions.

Saved in:
Bibliographic Details
Title: Computably enumerable equivalence relations via primitive recursive reductions.
Authors: Kalmurzayev, Birzhan S1 (AUTHOR), Bazhenov, Nikolay A2 (AUTHOR), Iskakov, Alibek M1 (AUTHOR)
Source: Journal of Logic & Computation. Mar2025, Vol. 35 Issue 2, p1-31. 31p.
Subjects: Recursive functions, Natural numbers, Classification, Literature
Abstract: The complexity classification of computably enumerable equivalence relations (or ceers, for short) has received much attention in the recent literature. A measure of complexity is typically provided by an appropriate notion of a reduction. Given binary relations |$R$| and |$S$| on natural numbers, a total function |$f$| is a reduction from |$R$| to |$S$| if for arbitrary |$x$| and |$y$|⁠ , the conditions |$x~R~y$| and |$f(x)~S~f(y)$| are always equivalent. If the function |$f$| can be chosen primitive recursive, then we say that |$R$| is primitively recursively reducible to |$S$|⁠ , denoted by |$R \leq _{pr} S$|⁠. We investigate the degree structure |$(\textbf {Ceers},\leq _{pr})$| of |$\leq _{pr}$| -degrees of ceers. We examine when pairs of incomparable degrees have an infimum and a supremum. In particular, we show that |$(\textbf {Ceers},\leq _{pr})$| is neither an upper semilattice nor a lower semilattice. We also study first-order definable subclasses of |$(\textbf {Ceers},\leq _{pr})$|⁠. In particular, we prove that the set of equivalences that have only finitely many classes is definable in |$(\textbf {Ceers},\leq _{pr})$|⁠. Finally, we show that the structure of |$\leq _{pr}$| -degrees of computably enumerable preorders has a hereditarily undecidable theory. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA 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: 184348323
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Computably enumerable equivalence relations via primitive recursive reductions.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Kalmurzayev%2C+Birzhan+S%22">Kalmurzayev, Birzhan S</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Bazhenov%2C+Nikolay+A%22">Bazhenov, Nikolay A</searchLink><relatesTo>2</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Iskakov%2C+Alibek+M%22">Iskakov, Alibek M</searchLink><relatesTo>1</relatesTo> (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Logic+%26+Computation%22">Journal of Logic & Computation</searchLink>. Mar2025, Vol. 35 Issue 2, p1-31. 31p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Recursive+functions%22">Recursive functions</searchLink><br /><searchLink fieldCode="DE" term="%22Natural+numbers%22">Natural numbers</searchLink><br /><searchLink fieldCode="DE" term="%22Classification%22">Classification</searchLink><br /><searchLink fieldCode="DE" term="%22Literature%22">Literature</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: The complexity classification of computably enumerable equivalence relations (or ceers, for short) has received much attention in the recent literature. A measure of complexity is typically provided by an appropriate notion of a reduction. Given binary relations |$R$| and |$S$| on natural numbers, a total function |$f$| is a reduction from |$R$| to |$S$| if for arbitrary |$x$| and |$y$|⁠ , the conditions |$x~R~y$| and |$f(x)~S~f(y)$| are always equivalent. If the function |$f$| can be chosen primitive recursive, then we say that |$R$| is primitively recursively reducible to |$S$|⁠ , denoted by |$R \leq _{pr} S$|⁠. We investigate the degree structure |$(\textbf {Ceers},\leq _{pr})$| of |$\leq _{pr}$| -degrees of ceers. We examine when pairs of incomparable degrees have an infimum and a supremum. In particular, we show that |$(\textbf {Ceers},\leq _{pr})$| is neither an upper semilattice nor a lower semilattice. We also study first-order definable subclasses of |$(\textbf {Ceers},\leq _{pr})$|⁠. In particular, we prove that the set of equivalences that have only finitely many classes is definable in |$(\textbf {Ceers},\leq _{pr})$|⁠. Finally, we show that the structure of |$\leq _{pr}$| -degrees of computably enumerable preorders has a hereditarily undecidable theory. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA 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=184348323
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1093/logcom/exad082
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 31
        StartPage: 1
    Subjects:
      – SubjectFull: Recursive functions
        Type: general
      – SubjectFull: Natural numbers
        Type: general
      – SubjectFull: Classification
        Type: general
      – SubjectFull: Literature
        Type: general
    Titles:
      – TitleFull: Computably enumerable equivalence relations via primitive recursive reductions.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Kalmurzayev, Birzhan S
      – PersonEntity:
          Name:
            NameFull: Bazhenov, Nikolay A
      – PersonEntity:
          Name:
            NameFull: Iskakov, Alibek M
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 03
              Text: Mar2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 0955792X
          Numbering:
            – Type: volume
              Value: 35
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: Journal of Logic & Computation
              Type: main
ResultId 1