Index Set of Structures with Two Equivalence Relations That Are Autostable Relative to Strong Constructivizations

详细

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.