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.
Citation:
M. I. Marchuk, “Index set of structures with two equivalence relations that are autostable relative to strong constructivizations”, Algebra Logika, 55:4 (2016), 465–477; Algebra and Logic, 55:4 (2016), 306–314
\Bibitem{Mar16}
\by M.~I.~Marchuk
\paper Index set of structures with two equivalence relations that are autostable relative to strong constructivizations
\jour Algebra Logika
\yr 2016
\vol 55
\issue 4
\pages 465--477
\mathnet{http://mi.mathnet.ru/al753}
\crossref{https://doi.org/10.17377/alglog.2016.55.406}
\transl
\jour Algebra and Logic
\yr 2016
\vol 55
\issue 4
\pages 306--314
\crossref{https://doi.org/10.1007/s10469-016-9400-y}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000388103400006}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84994703269}
Linking options:
https://www.mathnet.ru/eng/al753
https://www.mathnet.ru/eng/al/v55/i4/p465
This publication is cited in the following 14 articles:
N. A. Bazhenov, M. I. Marchuk, “O spektrakh razreshimoi kategorichnosti dlya pochti prostykh modelei”, Algebra i logika, 62:4 (2023), 441–457
N. A. Bazhenov, M. I. Marchuk, “Decidable Categoricity Spectra for Almost Prime Models”, Algebra Logic, 62:4 (2023), 291
Bazhenov N. Tsai H.-Ch., “On the Effective Universality of Mereological Theories”, Math. Log. Q., 68:1 (2022), 48–66
M. I. Marchuk, “Razreshimaya kategorichnost pochti prostykh modelei signatury grafov”, Matem. tr., 24:1 (2021), 117–141
N. Bazhenov, “HKSS-completeness of modal algebras”, Sib. elektron. matem. izv., 18:2 (2021), 923–930
N. A. Bazhenov, M. I. Marchuk, “On categoricity spectra for locally finite graphs”, Siberian Math. J., 62:5 (2021), 796–804
M. I. Marchuk, “The Index Set of the Class of Autostable Ordered Abelian
Groups”, Sib. Adv. Math., 31:1 (2021), 40
M. I. Marchuk, “On Decidable Categoricity for Almost Prime Models of the Signature of Graphs”, Sib. Adv. Math., 31:4 (2021), 283
M. I. Marchuk, “Indeksnoe mnozhestvo avtoustoichivykh uporyadochennykh abelevykh grupp”, Matem. tr., 23:1 (2020), 169–176
N. Bazhenov, M. Marchuk, “A note on decidable categoricity and index sets”, Sib. elektron. matem. izv., 17 (2020), 1013–1026
S. S. Goncharov, V. Harizanov, R. Miller, “On Decidable Categoricity and Almost Prime
Models”, Sib. Adv. Math., 30:3 (2020), 200
N. Bazhenov, “Computable contact algebras”, Fundam. Inform., 167:4 (2019), 257–269
N. A. Bazhenov, “Categoricity spectra of computable structures”, J. Math. Sci. (N. Y.), 256:1 (2021), 34–50
S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “The index set of the groups autostable relative to strong constructivizations”, Siberian Math. J., 58:1 (2017), 72–77
Citation in format AMSBIB
Contact us: