zbMATH — the first resource for mathematics

Index sets of constructive models of bounded signature that are autostable relative to strong constructivizations. (English. Russian original) Zbl 1347.03069
Algebra Logic 54, No. 2, 108-126 (2015); translation from Algebra Logika 54, No. 2, 163-192 (2015).
Summary: We evaluate algorithmic complexity of the class of computable models of bounded signature that have a strong constructivization and are autostable relative to strong constructivizations.

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
Full Text: DOI
[1] Goncharov, SS; Knight, JF, “computable structure and non-structure theorems”, Algebra and Logic, 41, 351-373, (2002)
[2] A. T. Nurtazin, “Computable classes and algebraic criteria for autostability,” Ph. D. Thesis, Institute of Mathematics and Mechanics, Alma-Ata (1974).
[3] S. S. Goncharov and Yu. L. Ershov, Constructive Models, Sib. School Alg. Log. [in Russian], Nauch. Kniga, Novosibirsk (1996). · Zbl 1043.03518
[4] Goncharov, SS, The problem of the number of non-autoequivalent constructivizations, Dokl. Akad. Nauk SSSR, 251, 271-274, (1980)
[5] S. S. Goncharov, “Computability and computable models,” in: Int. Math. Ser. (New York), 5, Springer, New York (2007), pp. 99-216. · Zbl 1143.03017
[6] Fokina, EB, Index sets of decidable models, Sib. Math. J., 48, 939-948, (2007) · Zbl 1148.53310
[7] Pavlovskii, EN, Estimation of the algorithmic complexity of classes of computable models, Sib. Math. J., 49, 512-523, (2008)
[8] Pavlovskii, EN, Index sets of prime model, Sib. El. Mat. Izv., 5, 200-210, (2008) · Zbl 1299.03043
[9] Yu. L. Ershov and E. A. Palyutin, Mathematical Logic [in Russian], 6th ed., Fizmatlit, Moscow (2011).
[10] H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967). · Zbl 0183.01401
[11] Goncharov, SS; Nurtazin, AT, “constructive models of complete solvable theories”, Algebra and Logic, 12, 67-77, (1973) · Zbl 0282.02018
[12] Nurtazin, AT, “strong and weak constructivizations and computable families”, Algebra and Logic, 13, 177-184, (1974) · Zbl 0305.02061
[13] S. S. Goncharov, “Index sets of almost prime constructive models,” Vestnik NGU, Mat., Mekh., Inf., 13, No. 3, 38-52 (2013). · Zbl 1289.03027
[14] Goncharov, SS; Khoussainov, B, “complexity of categorical theories with computable models”, Algebra and Logic, 43, 365-373, (2004) · Zbl 1097.03027
[15] S. S. Goncharov, Countable Boolean Algebras and Decidability, Sib. School Alg. Log. [in Russian], Nauch. Kniga, Novosibirsk (1996). · Zbl 0902.03021
[16] Peretyatkin, MG, “strongly constructive models and enumerations for the Boolean algebra of recursive sets”, Algebra and Logic, 10, 332-345, (1971) · Zbl 0311.02051
[17] Marker, D, Non σ_{\(n\)} axiomatizable almost strongly minimal theories, J. Symb. Log., 54, 921-927, (1989) · Zbl 0698.03021
[18] Goncharov, SS; Marchuk, MI, “index sets of constructive models that are autostable under strong constructivizations,”, Vestnik NGU, Mat., Mekh., Inf., 13, 43-67, (2013) · Zbl 1349.03037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.