{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T06:18:08Z","timestamp":1774592288456,"version":"3.50.1"},"reference-count":48,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2016,10,14]],"date-time":"2016-10-14T00:00:00Z","timestamp":1476403200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:p>We study autostability spectra relative to strong constructivizations (SC-autostability spectra). For a decidable structure<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S096012951600030X_inline1\"\/><jats:tex-math>$\\mathcal{S}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, the SC-autostability spectrum of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S096012951600030X_inline1\"\/><jats:tex-math>$\\mathcal{S}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is the set of all Turing degrees capable of computing isomorphisms among arbitrary decidable copies of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S096012951600030X_inline1\"\/><jats:tex-math>$\\mathcal{S}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. The degree of SC-autostability for<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S096012951600030X_inline1\"\/><jats:tex-math>$\\mathcal{S}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is the least degree in the spectrum (if such a degree exists).<\/jats:p><jats:p>We prove that for a computable successor ordinal \u03b1, every Turing degree c.e. in and above<jats:bold>0<\/jats:bold><jats:sup>(\u03b1)<\/jats:sup>is the degree of SC-autostability for some decidable structure. We show that for an infinite computable ordinal \u03b2, every Turing degree c.e. in and above<jats:bold>0<\/jats:bold><jats:sup>(2\u03b2+1)<\/jats:sup>is the degree of SC-autostability for some discrete linear order. We prove that the set of all PA-degrees is an SC-autostability spectrum. We also obtain similar results for autostability spectra relative to<jats:italic>n<\/jats:italic>-constructivizations.<\/jats:p>","DOI":"10.1017\/s096012951600030x","type":"journal-article","created":{"date-parts":[[2016,10,15]],"date-time":"2016-10-15T05:59:49Z","timestamp":1476511189000},"page":"392-411","source":"Crossref","is-referenced-by-count":13,"title":["Autostability spectra for decidable structures"],"prefix":"10.1017","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5834-2770","authenticated-orcid":false,"given":"NIKOLAY","family":"BAZHENOV","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2016,10,14]]},"reference":[{"key":"S096012951600030X_ref30","volume-title":"Countable Boolean Algebras and Decidability","author":"Goncharov","year":"1997"},{"key":"S096012951600030X_ref27","first-page":"142","article-title":"Linear orderings. Coding theorems","volume":"154","author":"Frolov","year":"2012","journal-title":"Uchenye Zapiski Kazanskogo Universiteta, Seriya Fiziko-Matematicheskie Nauki. Kazan"},{"key":"S096012951600030X_ref41","first-page":"1431","article-title":"On recursive abelian groups","volume":"32","author":"Mal'tsev","year":"1962","journal-title":"Soviet Mathematics \u2013 Doklady"},{"key":"S096012951600030X_ref43","unstructured":"Miller R. , Poonen B. , Schoutens H. and Shlapentokh A. (to appear). A computable functor from graphs to fields. arXiv:1510.07322"},{"key":"S096012951600030X_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-015-9362-5"},{"key":"S096012951600030X_ref35","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-015-9331-z"},{"key":"S096012951600030X_ref16","doi-asserted-by":"publisher","DOI":"10.2307\/2274481"},{"key":"S096012951600030X_ref39","doi-asserted-by":"publisher","DOI":"10.2307\/1968352"},{"key":"S096012951600030X_ref17","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1245158098"},{"key":"S096012951600030X_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90004-L"},{"key":"S096012951600030X_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90015-8"},{"key":"S096012951600030X_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2014.09.022"},{"key":"S096012951600030X_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00087-2"},{"key":"S096012951600030X_ref36","doi-asserted-by":"publisher","DOI":"10.1134\/S1064562415020106"},{"key":"S096012951600030X_ref18","doi-asserted-by":"publisher","DOI":"10.1215\/00294527-1960479"},{"key":"S096012951600030X_ref48","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71117-0"},{"key":"S096012951600030X_ref33","doi-asserted-by":"publisher","DOI":"10.1134\/S0037446615030039"},{"key":"S096012951600030X_ref13","unstructured":"Bazhenov N.A. (to appear). Degrees of autostability for linear orderings and linearly ordered abelian groups. Algebra Logic"},{"key":"S096012951600030X_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20028-6_12"},{"key":"S096012951600030X_ref26","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1956.0003"},{"key":"S096012951600030X_ref45","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(84)90028-9"},{"key":"S096012951600030X_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s10958-014-2032-7"},{"key":"S096012951600030X_ref23","doi-asserted-by":"publisher","DOI":"10.1215\/00294527-3322017"},{"key":"S096012951600030X_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-013-9233-x"},{"key":"S096012951600030X_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-016-9381-x"},{"key":"S096012951600030X_ref19","first-page":"823","volume-title":"Handbook of Recursive Mathematics","author":"Downey","year":"1998"},{"key":"S096012951600030X_ref15","volume-title":"Model Theory","author":"Chang","year":"1973"},{"key":"S096012951600030X_ref7","volume-title":"Computable Structures and the Hyperarithmetical Hierarchy","author":"Ash","year":"2000"},{"key":"S096012951600030X_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-015-9311-3"},{"key":"S096012951600030X_ref32","doi-asserted-by":"publisher","DOI":"10.1134\/S106456241505004X"},{"key":"S096012951600030X_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4305-3"},{"key":"S096012951600030X_ref21","first-page":"17","article-title":"Decidability of the elementary theory of distributive lattices with relative complements and the theory of filters","volume":"3","author":"Ershov","year":"1964","journal-title":"Algebra Logika"},{"key":"S096012951600030X_ref3","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1986-0860377-7"},{"key":"S096012951600030X_ref31","doi-asserted-by":"publisher","DOI":"10.1134\/S0081543811060071"},{"key":"S096012951600030X_ref44","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-06093-5"},{"key":"S096012951600030X_ref42","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1254748694"},{"key":"S096012951600030X_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.02.001"},{"key":"S096012951600030X_ref38","first-page":"33","article-title":"\u03a00 1 classes and degrees of theories","volume":"173","author":"Jockusch","year":"1972","journal-title":"Transactions of the American Mathematical Society"},{"key":"S096012951600030X_ref46","volume-title":"Linear Orderings","author":"Rosenstein","year":"1982"},{"key":"S096012951600030X_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01669456"},{"key":"S096012951600030X_ref2","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1215\/00294527-3496154","article-title":"Degrees that are not degrees of categoricity","volume":"57","author":"Anderson","year":"2016","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"S096012951600030X_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(87)90038-8"},{"key":"S096012951600030X_ref40","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n03ABEH001120"},{"key":"S096012951600030X_ref1","doi-asserted-by":"publisher","DOI":"10.1023\/B:SIMJ.0000042470.59162.9c"},{"key":"S096012951600030X_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90048-5"},{"key":"S096012951600030X_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-015-9353-6"},{"key":"S096012951600030X_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-009-0160-4"},{"key":"S096012951600030X_ref47","unstructured":"Scott D. (1962). Algebras of sets binumerable in complete extensions of arithmetic. In: Proceedings of Symposia in Pure Mathematics, volume V, American Mathematical Society 117\u2013121."}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096012951600030X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,26]],"date-time":"2020-09-26T17:34:15Z","timestamp":1601141655000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096012951600030X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,14]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["S096012951600030X"],"URL":"https:\/\/doi.org\/10.1017\/s096012951600030x","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,14]]}}}