Email this article Index Set of Structures with Two Equivalence Relations That Are Autostable Relative to Strong Constructivizations
- Authors: Marchuk M.I.1,2
-
Affiliations:
- Sobolev Institute of Mathematics
- Novosibirsk State University
- Issue: Vol 55, No 4 (2016)
- Pages: 306-314
- Section: Article
- URL: https://journal-vniispk.ru/0002-5232/article/view/233995
- DOI: https://doi.org/10.1007/s10469-016-9400-y
- ID: 233995
Cite item
Open Access
Access granted
Subscription Access
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.
About the authors
M. I. Marchuk
Sobolev Institute of Mathematics; Novosibirsk State University
Author for correspondence.
Email: margaretmarchuk@gmail.com
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090
Supplementary files
