RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Algebra Logika:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Algebra Logika, 2016, Volume 55, Number 4, Pages 465–477 (Mi al753)  

This article is cited in 3 scientific papers (total in 3 papers)

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

M. I. Marchukab

a 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.

Funding Agency Grant Number
Russian Foundation for Basic Research 14-01-00376
Supported by RFBR, project No. 14-01-00376.


DOI: https://doi.org/10.17377/alglog.2016.55.406

Full text: PDF file (174 kB)
References: PDF file   HTML file

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

Bibliographic databases:

UDC: 510.5+512.563
Received: 25.02.2016
Revised: 17.07.2016

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

Citation in format AMSBIB
\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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000388103400006}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84994703269}


Linking options:
  • http://mi.mathnet.ru/eng/al753
  • http://mi.mathnet.ru/eng/al/v55/i4/p465

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. N. A. Bazhenov, “Spektry kategorichnosti vychislimykh struktur”, Trudy seminara kafedry algebry i matematicheskoi logiki Kazanskogo (Privolzhskogo) federalnogo universiteta, Itogi nauki i tekhn. Ser. Sovrem. mat. i ee pril. Temat. obz., 157, VINITI RAN, M., 2018, 42–58  mathnet
    2. N. Bazhenov, “Computable contact algebras”, Fundam. Inform., 167:4 (2019), 257–269  crossref  mathscinet  zmath  isi  scopus
    3. M. I. Marchuk, “Indeksnoe mnozhestvo avtoustoichivykh uporyadochennykh abelevykh grupp”, Matem. tr., 23:1 (2020), 169–176  mathnet  crossref
  • Алгебра и логика Algebra and Logic
    Number of views:
    This page:102
    Full text:6
    References:20
    First page:9

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020