General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Algebra Logika:

Personal entry:
Save password
Forgotten password?

Algebra Logika, 2004, Volume 43, Number 6, Pages 650–665 (Mi al101)  

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

Complexity of Categorical Theories with Computable Models

S. S. Goncharova, B. Khoussainovb

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b University of Auckland

Abstract: M. Lerman and J. Scmerl specified some sufficient conditions for computable models of countably categorical arithmetical theories to exist. More precisely, it was shown that if $T$ is a countably categorical arithmetical theory, and the set of its sentences beginning with an existential quantifier and having at most $n+1$ alternations of quantifiers is $\Sigma_{n+1}^0$ for any $n$, then $T$ has a computable model. J. Night improved this result by allowing certain uniformity and omitting the requirement that $T$ is arithmetical. However, all of the known examples of theories of $\aleph_0$-categorical computable models had low level of algorithmic complexity, and whether there are theories that would satisfy the above conditions for sufficiently large $n$ was unknown. This paper will include such examples.

Keywords: computable model, countably categorical theory

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

English version:
Algebra and Logic, 2004, 43:6, 365–373

Bibliographic databases:

UDC: 510.53+510.67
Received: 08.09.2002
Revised: 16.09.2003

Citation: S. S. Goncharov, B. Khoussainov, “Complexity of Categorical Theories with Computable Models”, Algebra Logika, 43:6 (2004), 650–665; Algebra and Logic, 43:6 (2004), 365–373

Citation in format AMSBIB
\by S.~S.~Goncharov, B.~Khoussainov
\paper Complexity of Categorical Theories with Computable Models
\jour Algebra Logika
\yr 2004
\vol 43
\issue 6
\pages 650--665
\jour Algebra and Logic
\yr 2004
\vol 43
\issue 6
\pages 365--373

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. A. N. Gavryushkin, “Complexity of Ehrenfeucht models”, Algebra and Logic, 45:5 (2006), 289–295  mathnet  crossref  mathscinet  zmath
    2. A. N. Gavryushkin, “Spectra of computable models for Ehrenfeucht theories”, Algebra and Logic, 46:3 (2007), 149–157  mathnet  crossref  mathscinet  zmath  isi
    3. E. B. Fokina, “Index sets of decidable models”, Siberian Math. J., 48:5 (2007), 939–948  mathnet  crossref  mathscinet  zmath  isi
    4. Khoussainov B.M., Laskowski M.C., Lempp S., Solomon R., “On the computability-theoretic complexity of trivial, strongly minimal models”, Proc. Amer. Math. Soc., 135:11 (2007), 3711–3721  crossref  mathscinet  zmath  isi  elib  scopus
    5. Fokina E.B., “Index sets of computable structures with decidable theories”, Computation and Logic in the Real World, Proceedings, Lecture Notes in Computer Science, 4497, 2007, 290–296  crossref  mathscinet  zmath  isi  scopus
    6. Soskova A.A., “A jump inversion theorem for the degree spectra”, Computation and Logic in the Real World, Proceedings, Lecture Notes in Computer Science, 4497, 2007, 716–726  crossref  mathscinet  zmath  isi  scopus
    7. 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
    8. S. S. Goncharov, “Algoritmicheskaya slozhnost schetnykh modelei silno minimalnykh teorii”, Vestn. NGU. Ser. matem., mekh., inform., 8:2 (2008), 38–53  mathnet
    9. 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
    10. Soskova A., Soskov I.N., “A jump inversion theorem for the degree spectra”, J. Logic Comput., 19:1 (2009), 199–215  crossref  mathscinet  zmath  isi  scopus
    11. A. I. Stukachev, “A jump inversion theorem for the semilattices of $\Sigma$-degrees”, Siberian Advances in Mathematics, 20:1 (2010), 68–74  mathnet  crossref  mathscinet
    12. Fokina E.B., Kalimullin I., Miller R., “Degrees of categoricity of computable structures”, Arch. Math. Logic, 49:1 (2010), 51–67  crossref  mathscinet  zmath  isi  scopus
    13. Khoussainov B., Montalban A., “A Computable N-0-Categorical Structure Whose Theory Computes True Arithmetic”, Journal of Symbolic Logic, 75:2 (2010), 728–740  crossref  mathscinet  zmath  isi  scopus
    14. Montalban A., “Rice Sequences of Relations”, Philos. Trans. R. Soc. A-Math. Phys. Eng. Sci., 370:1971, SI (2012), 3464–3487  crossref  mathscinet  zmath  adsnasa  isi  scopus
    15. 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
    16. 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
    17. S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “The index set of Boolean algebras autostable relative to strong constructivizations”, Siberian Math. J., 56:3 (2015), 393–404  mathnet  crossref  crossref  mathscinet  isi  elib  elib
    18. 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
    19. E. B. Fokina, S. S. Goncharov, V. Harizanov, O. V. Kudinov, D. Turetsky, “Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations”, Algebra and Logic, 54:4 (2015), 336–341  mathnet  crossref  crossref  mathscinet  isi
    20. Soskova A.A. Soskova M.I., “Enumeration Reducibility and Computable Structure Theory”, Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60Th Birthday, Lecture Notes in Computer Science, 10010, ed. Day A. Fellows M. Greenberg N. Khoussainov B. Melnikov A. Rosamond F., Springer International Publishing Ag, 2017, 271–301  crossref  mathscinet  zmath  isi  scopus
    21. Andrews U., Knight J.F., “Strongly Minimal Theories With Recursive Models”, J. Eur. Math. Soc., 20:7 (2018), 1561–1594  crossref  mathscinet  zmath  isi  scopus
  • Алгебра и логика Algebra and Logic
    Number of views:
    This page:419
    Full text:114
    First page:1

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