Standard

Autostability spectra for decidable structures. / Bazhenov, Nikolay.

In: Mathematical Structures in Computer Science, Vol. 28, No. 3, 01.03.2018, p. 392-411.

Research output: Contribution to journal › Article › peer-review

Harvard

Bazhenov, N 2018, 'Autostability spectra for decidable structures', Mathematical Structures in Computer Science, vol. 28, no. 3, pp. 392-411. https://doi.org/10.1017/S096012951600030X

APA

Bazhenov, N. (2018). Autostability spectra for decidable structures. Mathematical Structures in Computer Science, 28(3), 392-411. https://doi.org/10.1017/S096012951600030X

Vancouver

Bazhenov N. Autostability spectra for decidable structures. Mathematical Structures in Computer Science. 2018 Mar 1;28(3):392-411. doi: 10.1017/S096012951600030X

Author

Bazhenov, Nikolay. / Autostability spectra for decidable structures. In: Mathematical Structures in Computer Science. 2018 ; Vol. 28, No. 3. pp. 392-411.

BibTeX

@article{ca03f3c63fa54fdc8c2efd568d767a2a,
title = "Autostability spectra for decidable structures",
abstract = "We study autostability spectra relative to strong constructivizations (SC-autostability spectra). For a decidable structure , the SC-autostability spectrum of is the set of all Turing degrees capable of computing isomorphisms among arbitrary decidable copies of . The degree of SC-autostability for is the least degree in the spectrum (if such a degree exists). We prove that for a computable successor ordinal α, every Turing degree c.e. in and above 0 (α) is the degree of SC-autostability for some decidable structure. We show that for an infinite computable ordinal β, every Turing degree c.e. in and above 0 (2β+1) 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 n-constructivizations.",
keywords = "STRONG CONSTRUCTIVIZATIONS, BOOLEAN-ALGEBRAS, INDEX SETS, COMPUTABLE CATEGORICITY, RECURSIVE STRUCTURES, HYPERARITHMETICAL DEGREES, LINEAR-ORDERINGS, MODELS, COMPLEXITY, STABILITY",
author = "Nikolay Bazhenov",
year = "2018",
month = mar,
day = "1",
doi = "10.1017/S096012951600030X",
language = "English",
volume = "28",
pages = "392--411",
journal = "Mathematical Structures in Computer Science",
issn = "0960-1295",
publisher = "Cambridge University Press",
number = "3",

}

RIS

TY - JOUR

T1 - Autostability spectra for decidable structures

AU - Bazhenov, Nikolay

PY - 2018/3/1

Y1 - 2018/3/1

N2 - We study autostability spectra relative to strong constructivizations (SC-autostability spectra). For a decidable structure , the SC-autostability spectrum of is the set of all Turing degrees capable of computing isomorphisms among arbitrary decidable copies of . The degree of SC-autostability for is the least degree in the spectrum (if such a degree exists). We prove that for a computable successor ordinal α, every Turing degree c.e. in and above 0 (α) is the degree of SC-autostability for some decidable structure. We show that for an infinite computable ordinal β, every Turing degree c.e. in and above 0 (2β+1) 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 n-constructivizations.

AB - We study autostability spectra relative to strong constructivizations (SC-autostability spectra). For a decidable structure , the SC-autostability spectrum of is the set of all Turing degrees capable of computing isomorphisms among arbitrary decidable copies of . The degree of SC-autostability for is the least degree in the spectrum (if such a degree exists). We prove that for a computable successor ordinal α, every Turing degree c.e. in and above 0 (α) is the degree of SC-autostability for some decidable structure. We show that for an infinite computable ordinal β, every Turing degree c.e. in and above 0 (2β+1) 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 n-constructivizations.

KW - STRONG CONSTRUCTIVIZATIONS

KW - BOOLEAN-ALGEBRAS

KW - INDEX SETS

KW - COMPUTABLE CATEGORICITY

KW - RECURSIVE STRUCTURES

KW - HYPERARITHMETICAL DEGREES

KW - LINEAR-ORDERINGS

KW - MODELS

KW - COMPLEXITY

KW - STABILITY

UR - http://www.scopus.com/inward/record.url?scp=84991253027&partnerID=8YFLogxK

U2 - 10.1017/S096012951600030X

DO - 10.1017/S096012951600030X

M3 - Article

AN - SCOPUS:84991253027

VL - 28

SP - 392

EP - 411

JO - Mathematical Structures in Computer Science

JF - Mathematical Structures in Computer Science

SN - 0960-1295

IS - 3

ER -

ID: 12177864