{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T12:07:36Z","timestamp":1753877256433,"version":"3.41.2"},"reference-count":18,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"name":"Science Committee of the Ministry of Science and Higher Education of the Republic of Kazakhstan","award":["AP19576325"],"award-info":[{"award-number":["AP19576325"]}]},{"name":"Nazarbayev University Faculty Development Competitive Research","award":["201223FD8823"],"award-info":[{"award-number":["201223FD8823"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,4,24]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Let $\\mathbf{C}^{pr}_{m}$ be the upper semilattice of degrees of computable sets with respect to primitive recursive $m$-reducibility. We prove that the first-order theory of $\\mathbf{C}^{pr}_{m}$ is hereditarily undecidable.<\/jats:p>","DOI":"10.1093\/logcom\/exae074","type":"journal-article","created":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T12:43:24Z","timestamp":1731069804000},"source":"Crossref","is-referenced-by-count":0,"title":["Undecidability of the degree structure of primitive recursive <i>m<\/i>-reducibility"],"prefix":"10.1093","volume":"35","author":[{"given":"Birzhan S","family":"Kalmurzayev","sequence":"first","affiliation":[{"name":", Kazakh-British Technical University , 59 Tole Bi Street, Almaty 050000 ,","place":["Kazakhstan"]}]},{"given":"Nikolay A","family":"Bazhenov","sequence":"additional","affiliation":[{"name":", Kazakh-British Technical University , 59 Tole Bi Street, Almaty 050000 ,","place":["Kazakhstan"]},{"name":"Nazarbayev University , 53 Qabanbaybatyr Avenue, Astana 010000 ,","place":["Kazakhstan"]}]},{"given":"Alibek M","family":"Iskakov","sequence":"additional","affiliation":[{"name":", Kazakh-British Technical University , 59 Tole Bi Street, Almaty 050000 ,","place":["Kazakhstan"]}]}],"member":"286","published-online":{"date-parts":[[2024,11,8]]},"reference":[{"key":"2025052505562655000_ref1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0020-0190(86)90054-2","article-title":"Inhomogeneities in the polynomial time degrees: the degrees of super sparse sets","volume":"22","author":"Ambos-Spies","year":"1986","journal-title":"Information Processing Letters"},{"key":"2025052505562655000_ref2","first-page":"683","article-title":"Polynomial time reducibilities and degrees","volume-title":"Handbook of Computability Theory, Volume 140 of Studies in Logic and the Foundations of Mathematics","author":"Ambos-Spies","year":"1999"},{"key":"2025052505562655000_ref3","first-page":"209","article-title":"The theory of the polynomial many-one degrees of recursive sets is undecidable","volume-title":"STACS 92, Proceedings, volume 577 of Lecture Notes in Computer Science","author":"Ambos-Spies","year":"1992"},{"key":"2025052505562655000_ref4","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1017\/bsl.2019.20","article-title":"Foundations of online structure theory","volume":"25","author":"Bazhenov","year":"2019","journal-title":"The Bulletin of Symbolic Logic"},{"key":"2025052505562655000_ref5","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1017\/S0960129522000093","article-title":"Rogers semilattices of punctual numberings","volume":"32","author":"Bazhenov","year":"2022","journal-title":"Mathematical Structures in Computer Science"},{"key":"2025052505562655000_ref6","doi-asserted-by":"crossref","first-page":"187","DOI":"10.3233\/COM-210375","article-title":"Primitive recursive equivalence relations and their primitive recursive complexity","volume":"11","author":"Bazhenov","year":"2022","journal-title":"Computability"},{"key":"2025052505562655000_ref7","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF02485250","article-title":"Lattice-theoretic decision problems in universal algebra","volume":"5","author":"Burris","year":"1975","journal-title":"Algebra Universalis"},{"key":"2025052505562655000_ref8","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1006\/jcss.1999.1678","article-title":"Undecidability results for low complexity time classes","volume":"60","author":"Downey","year":"2000","journal-title":"Journal of Computer and System Sciences"},{"key":"2025052505562655000_ref9","article-title":"Foundations of online structure theory II: the operator approach","volume":"17","author":"Downey","year":"2021","journal-title":"Logical Methods in Computer Science"},{"key":"2025052505562655000_ref10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1070\/RM1965v020n04ABEH001188","article-title":"Elementary theories","volume":"20","author":"Ershov","year":"1965","journal-title":"Russian Mathematical Surveys"},{"volume-title":"Countable Boolean Algebras and Decidability","year":"1997","author":"Goncharov","key":"2025052505562655000_ref11"},{"key":"2025052505562655000_ref12","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.tcs.2017.01.029","article-title":"Algebraic structures computable without delay","volume":"674","author":"Kalimullin","year":"2017","journal-title":"Theoretical Computer Science"},{"key":"2025052505562655000_ref13","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exad082","article-title":"Computably enumerable equivalence relations via primitive recursive reductions","author":"Kalmurzayev","year":"2024","journal-title":"Journal of Logic and Computation"},{"key":"2025052505562655000_ref14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","article-title":"Reducibility among combinatorial problems","volume-title":"Complexity of Computer Computations","author":"Karp","year":"1972"},{"key":"2025052505562655000_ref15","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","article-title":"On the structure of polynomial time reducibility","volume":"22","author":"Ladner","year":"1975","journal-title":"Journal of the Association for Computing Machinery"},{"key":"2025052505562655000_ref16","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1112\/S0024609397003548","article-title":"Intervals of the lattice of computably enumerable sets and effective Boolean algebras","volume":"29","author":"Nies","year":"1997","journal-title":"Bulletin of the London Mathematical Society"},{"key":"2025052505562655000_ref17","doi-asserted-by":"crossref","first-page":"4989","DOI":"10.1090\/S0002-9947-00-02652-0","article-title":"Effectively dense Boolean algebras and their applications","volume":"352","author":"Nies","year":"2000","journal-title":"Transactions of the American Mathematical Society"},{"volume-title":"Classical Recursion Theory, Volume 125 of Stud. Logic Found. Math","year":"1992","author":"Odifreddi","key":"2025052505562655000_ref18"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/4\/exae074\/60540739\/exae074.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/4\/exae074\/60540739\/exae074.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,25]],"date-time":"2025-05-25T09:56:49Z","timestamp":1748167009000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/doi\/10.1093\/logcom\/exae074\/7887467"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,8]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,4,24]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exae074","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"type":"print","value":"0955-792X"},{"type":"electronic","value":"1465-363X"}],"subject":[],"published-other":{"date-parts":[[2025,6]]},"published":{"date-parts":[[2024,11,8]]},"article-number":"exae074"}}