Geodesic
Index set of structures with two equivalence relations that are autostable relative to strong constructivizations
Algebra i logika, Tome 55 (2016) no. 4, pp. 465-477

Voir la notice de l'article provenant de la source Math-Net.Ru

We derive a bound on the algorithmic complexity for the class of computable structures with two equivalence relations that have a strong constructivization and are autostable relative to strong constructivizations. We construct codings of a linear order and of an automorphically nontrivial directed irreflexive graph into a structure with two equivalence relations. It is proved that such codings preserve the degree spectrum and $d$-computable dimension.
Keywords: autostability relative to strong constructivizations, computable structure, hyperarithmetical hierarchy, index set, irreflexive directed graph, coding, linear order, strongly constructivizable structure, structure with two equivalence relations. 
M. I. Marchuk. Index set of structures with two equivalence relations that are autostable relative to strong constructivizations. Algebra i logika, Tome 55 (2016) no. 4, pp. 465-477. http://geodesic.mathdoc.fr/item/AL_2016_55_4_a5/
@article{AL_2016_55_4_a5,
     author = {M. I. Marchuk},
     title = {Index set of structures with two equivalence relations that are autostable relative to strong constructivizations},
     journal = {Algebra i logika},
     pages = {465--477},
     year = {2016},
     volume = {55},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2016_55_4_a5/}
}
TY  - JOUR
AU  - M. I. Marchuk
TI  - Index set of structures with two equivalence relations that are autostable relative to strong constructivizations
JO  - Algebra i logika
PY  - 2016
SP  - 465
EP  - 477
VL  - 55
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/AL_2016_55_4_a5/
LA  - ru
ID  - AL_2016_55_4_a5
ER  - 
%0 Journal Article
%A M. I. Marchuk
%T Index set of structures with two equivalence relations that are autostable relative to strong constructivizations
%J Algebra i logika
%D 2016
%P 465-477
%V 55
%N 4
%U http://geodesic.mathdoc.fr/item/AL_2016_55_4_a5/
%G ru
%F AL_2016_55_4_a5

[1] S. S. Goncharov, Yu. L. Ershov, Konstruktivnye modeli, Sibirskaya shkola algebry i logiki, Nauchnaya kniga, Novosibirsk, 1999

[2] A. T. Nurtazin, Vychislimye klassy i algebraicheskie kriterii avtoustoichivosti, Diss. kand. fiz.-mat. nauk, Alma-Ata, 1974

[3] E. B. Fokina, “Indeksnye mnozhestva razreshimykh modelei”, Sib. matem. zh., 48:5 (2007), 1167–1179 | MR | Zbl

[4] S. S. Goncharov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei ogranichennoi signatury”, Algebra i logika, 54:2 (2015), 163–192 | DOI | MR | Zbl

[5] S. S. Goncharov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei konechnoi signatury i signatury grafov”, Algebra i logika, 54:6 (2015), 663–679 | DOI | MR

[6] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “Indeksnoe mnozhestvo avtoustoichivykh otnositelno silnykh konstruktivizatsii bulevykh algebr”, Sib. matem. zh., 56:3 (2015), 498–512 | DOI | MR | Zbl

[7] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “Indeksnoe mnozhestvo avtoustoichivykh otnositelno silnykh konstruktivizatsii lineinykh poryadkov”, Vestn. NGU. Ser. matem., mekh., inform., 15:3 (2015), 51–60 | Zbl

[8] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei estestvennykh klassov”, Dokl. AN, 464:1 (2015), 12–14 | DOI | MR | Zbl

[9] S. S. Goncharov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei”, Vestn. NGU. Ser. matem., mekh., inform., 13:4 (2013), 43–67 | Zbl

[10] S. S. Goncharov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei netrivialnykh signatur”, Dokl. AN, 461:2 (2015), 140–142 | DOI | MR | Zbl

[11] S. S. Goncharov, Dzh. Nait, “Vychislimye strukturnye i antistrukturnye teoremy”, Algebra i logika, 41:6 (2002), 639–681 | MR | Zbl

[12] J. F. Knight, “Degrees coded in jumps of orderings”, J. Symb. Log., 51:4 (1986), 1034–1042 | DOI | MR | Zbl

[13] U. Kalvert, D. Kammins, Dzh. F. Nait, S. Miller, “Sravnenie klassov konechnykh struktur”, Algebra i logika, 43:6 (2004), 666–701 | MR | Zbl

[14] J. F. Knight, S. Miller, M. Vanden Boom, “Turing computable embeddings”, J. Symb. Log., 72:3 (2007), 901–918 | DOI | MR | Zbl

[15] D. A. Tusupov, “Izomorfizmy i algoritmicheskie svoistva struktur s dvumya ekvivalentnostyami”, Algebra i logika, 55:1 (2016), 75–86 | DOI