Sibirskii Matematicheskii Zhurnal
General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Sibirsk. Mat. Zh.:

Personal entry:
Save password
Forgotten password?

Sibirsk. Mat. Zh., 2007, Volume 48, Number 5, Pages 1167–1179 (Mi smj1799)  

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

Index sets of decidable models

E. B. Fokina

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: We study the index sets of the class of $d$-decidable structures and of the class of $d$-decidable countably categorical structures, where $d$ is an arbitrary arithmetical Turing degree. It is proved that the first of them is $m$-complete $\Sigma^{0,d}_3$, and the second is $m$-complete $\Sigma^{0,d}_3\setminus\Sigma^{0,d}_3$ in the universal computable numbering of computable structures for the language with one binary predicate.

Keywords: index set, computable structure, decidable structure, countably categorical theory.

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

English version:
Siberian Mathematical Journal, 2007, 48:5, 939–948

Bibliographic databases:

UDC: 517.1+519.5
Received: 07.11.2006

Citation: E. B. Fokina, “Index sets of decidable models”, Sibirsk. Mat. Zh., 48:5 (2007), 1167–1179; Siberian Math. J., 48:5 (2007), 939–948

Citation in format AMSBIB
\by E.~B.~Fokina
\paper Index sets of decidable models
\jour Sibirsk. Mat. Zh.
\yr 2007
\vol 48
\issue 5
\pages 1167--1179
\jour Siberian Math. J.
\yr 2007
\vol 48
\issue 5
\pages 939--948

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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. E. N. Pavlovskii, “Estimation of the algorithmic complexity of classes of computable models”, Siberian Math. J., 49:3 (2008), 512–523  mathnet  crossref  mathscinet  zmath  isi
    2. E. N. Pavlovskii, “Indeksnye mnozhestva prostykh modelei”, Sib. elektron. matem. izv., 5 (2008), 200–210  mathnet  mathscinet
    3. E. B. Fokina, “Algoritmicheskie svoistva modelei signatury s dvumya odnomestnymi funktsionalnymi simvolami”, Vestn. NGU. Ser. matem., mekh., inform., 8:1 (2008), 90–101  mathnet
    4. Fokina E.B., “Index sets for some classes of structures”, Ann. Pure Appl. Logic, 157:2-3 (2009), 139–147  crossref  mathscinet  zmath  isi  elib  scopus
    5. S. S. Goncharov, “Index Sets of Almost Prime Constructive Models”, J. Math. Sci., 205:3 (2015), 355–367  mathnet  crossref
    6. N. A. Bazhenov, “Computable numberings of the class of Boolean algebras with distinguished endomorphisms”, Algebra and Logic, 52:5 (2013), 355–366  mathnet  crossref  mathscinet  isi
    7. S. S. Goncharov, M. I. Marchuk, “Index Sets of Autostable Relative to Strong Constructivizations Constructive Models”, J. Math. Sci., 205:3 (2015), 368–388  mathnet  crossref
    8. Fokina E.B., Harizanov V., Melnikov A., “Computable Model Theory”, Turing'S Legacy: Developments From Turing'S Ideas in Logic, Lecture Notes in Logic, 42, ed. Downey R., Cambridge Univ Press, 2014, 124–194  mathscinet  isi
    9. S. S. Goncharov, M. I. Marchuk, “Index sets of constructive models of bounded signature that are autostable relative to strong constructivizations”, Algebra and Logic, 54:2 (2015), 108–126  mathnet  crossref  crossref  mathscinet  isi
    10. S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “The index set of linear orderings that are autostable relative to strong constructivizations”, J. Math. Sci., 221:6 (2017), 840–848  mathnet  crossref  crossref
    11. S. S. Goncharov, M. I. Marchuk, “Index sets of constructive models of finite and graph signatures that are autostable relative to strong constructivizations”, Algebra and Logic, 54:6 (2016), 428–439  mathnet  crossref  crossref  mathscinet  isi
    12. Goncharov S.S., Bazhenov N.A., Marchuk M.I., “Index Sets of Autostable Relative To Strong Constructivizations Constructive Models For Familiar Classes”, Dokl. Math., 92:2 (2015), 525–527  crossref  zmath  isi  elib  scopus
    13. Goncharov S.S., Marchuk M.I., “Index Sets of Constructive Models of Nontrivial Signature Autostable Relative To Strong Constructivizations”, Dokl. Math., 91:2 (2015), 158–159  crossref  mathscinet  zmath  isi  elib  scopus
    14. N. A. Bazhenov, “Degrees of autostability relative to strong constructivizations for Boolean algebras”, Algebra and Logic, 55:2 (2016), 87–102  mathnet  crossref  crossref  isi
    15. M. I. Marchuk, “Index set of structures with two equivalence relations that are autostable relative to strong constructivizations”, Algebra and Logic, 55:4 (2016), 306–314  mathnet  crossref  crossref  isi
    16. Harrison-Trainor M., “There Is No Classification of the Decidably Presentable Structures”, J. Math. Log., 18:2 (2018), UNSP 1850010  crossref  mathscinet  isi  scopus
    17. Bazhenov N., Harrison-Trainor M., Kalimullin I., Melnikov A., Ng K.M., “Automatic and Polynomial-Time Algebraic Structures”, J. Symb. Log., 84:4 (2019), 1630–1669  crossref  mathscinet  zmath  isi  scopus
    18. N. Bazhenov, M. Marchuk, “A note on decidable categoricity and index sets”, Sib. elektron. matem. izv., 17 (2020), 1013–1026  mathnet  crossref
    19. M. I. Marchuk, “Razreshimaya kategorichnost pochti prostykh modelei signatury grafov”, Matem. tr., 24:1 (2021), 117–141  mathnet  crossref
  • —ибирский математический журнал Siberian Mathematical Journal
    Number of views:
    This page:344
    Full text:96

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022