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



Sibirsk. Mat. Zh.:
Year:
Volume:
Issue:
Page:
Find






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


Sibirsk. Mat. Zh., 2008, Volume 49, Number 3, Pages 635–649 (Mi smj1867)  

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

Estimation of the algorithmic complexity of classes of computable models

E. N. Pavlovskii

Novosibirsk State University, Mechanics and Mathematics Department

Abstract: We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models ($\Sigma_2^0$-complete), computable models with $\omega$-categorical theories ($\Delta_\omega^0$-complex $\Pi_{\omega+2}^0$-set), prime models ($\Delta_\omega^0$-complex $\Pi_{\omega+2}^0$-set), models with $\omega_1$-categorical theories ($\Delta_\omega^0$-complex $\Sigma_{\omega+1}^0$-set). We obtain a universal lower bound for the model-theoretic properties preserved by Marker's extensions ($\Delta_\omega^0$).

Keywords: computable model, index set.

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

English version:
Siberian Mathematical Journal, 2008, 49:3, 512–523

Bibliographic databases:

UDC: 510.67+510.5+510.635
Received: 14.06.2007
Revised: 04.04.2008

Citation: E. N. Pavlovskii, “Estimation of the algorithmic complexity of classes of computable models”, Sibirsk. Mat. Zh., 49:3 (2008), 635–649; Siberian Math. J., 49:3 (2008), 512–523

Citation in format AMSBIB
\Bibitem{Pav08}
\by E.~N.~Pavlovskii
\paper Estimation of the algorithmic complexity of classes of computable models
\jour Sibirsk. Mat. Zh.
\yr 2008
\vol 49
\issue 3
\pages 635--649
\mathnet{http://mi.mathnet.ru/smj1867}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2442543}
\zmath{https://zbmath.org/?q=an:1164.03334}
\transl
\jour Siberian Math. J.
\yr 2008
\vol 49
\issue 3
\pages 512--523
\crossref{https://doi.org/10.1007/s11202-008-0049-1}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000256329000013}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-44349121197}


Linking options:
  • http://mi.mathnet.ru/eng/smj1867
  • http://mi.mathnet.ru/eng/smj/v49/i3/p635

    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. E. N. Pavlovskii, “Indeksnye mnozhestva prostykh modelei”, Sib. elektron. matem. izv., 5 (2008), 200–210  mathnet  mathscinet
    2. S. S. Goncharov, “Index Sets of Almost Prime Constructive Models”, J. Math. Sci., 205:3 (2015), 355–367  mathnet  crossref
    3. 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
    4. 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
    5. 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
    6. 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
    7. 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
    8. 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
    9. 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
  • Сибирский математический журнал Siberian Mathematical Journal
    Number of views:
    This page:252
    Full text:71
    References:30
    First page:2

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