This article is cited in 13 papers

Index set of structures with two equivalence relations that are autostable relative to strong constructivizations

M. I. Marchuk<sup>ab

a</sup> Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090 Russia
^b Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090 Russia

Abstract: 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.

UDC: 510.5+512.563

Received: 25.02.2016
Revised: 17.07.2016

DOI: 10.17377/alglog.2016.55.406

 English version: Algebra and Logic, 2016, 55:4, 306–314

Bibliographic databases:

• 
•