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

Algebra i logika

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	General information
	Latest issue
	Archive
	Impact factor

	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 i logika, 2004, Volume 43, Number 6, Pages 650–665 (Mi al101)

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

Complexity of Categorical Theories with Computable Models

S. S. Goncharov^a, B. Khoussainov^b

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

Full-text PDF (218 kB) Citations (31)

References:

PDF

HTML

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

$T$ is a countably categorical arithmetical theory, and the set of its sentences beginning with an existential quantifier and having at most

n + 1

$n+1$ alternations of quantifiers is

Σ_{n + 1}^{0}

$\Sigma_{n+1}^0$ for any

n

$n$ , then

T

$T$ has a computable model. J. Night improved this result by allowing certain uniformity and omitting the requirement that

T

$T$ is arithmetical. However, all of the known examples of theories of

ℵ_{0}

$\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

$n$ was unknown. This paper will include such examples.

Keywords: computable model, countably categorical theory.

Received: 08.09.2002
Revised: 16.09.2003

English version:
Algebra and Logic, 2004, Volume 43, Issue 6, Pages 365–373
DOI: https://doi.org/10.1023/B:ALLO.0000048826.92325.02

Bibliographic databases:

UDC: 510.53+510.67

Language: Russian

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

\Bibitem{GonKho04}

\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

\mathnet{http://mi.mathnet.ru/al101}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2135386}

\zmath{https://zbmath.org/?q=an:1097.03027}

\transl

\jour Algebra and Logic

\yr 2004

\vol 43

\issue 6

\pages 365--373

\crossref{https://doi.org/10.1023/B:ALLO.0000048826.92325.02}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-35148837362}

Linking options:

https://www.mathnet.ru/eng/al101

https://www.mathnet.ru/eng/al/v43/i6/p650

This publication is cited in the following 31 articles:

I. Sh. Kalimullin, V. G. Puzarenko, M. Kh. Faizrahmanov, “Semidecidable numberings in admissible sets”, Algebra and Logic, 59:3 (2020), 273–277
Andrews U., Knight J.F., “Strongly Minimal Theories With Recursive Models”, J. Eur. Math. Soc., 20:7 (2018), 1561–1594
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
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
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
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
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
Ekaterina B. Fokina, Valentina Harizanov, Alexander Melnikov, Turing's Legacy, 2014, 124
S. S. Goncharov, M. I. Marchuk, “Index Sets of Autostable Relative to Strong Constructivizations Constructive Models”, J. Math. Sci., 205:3 (2015), 368–388
Alexey Stukachev, Effective Mathematics of the Uncountable, 2013, 164
I. N. Soskov, “Effective properties of Marker's extensions”, Journal of Logic and Computation, 23:6 (2013), 1335
E. Fokina, S.-D. Friedman, J. Knight, R. Miller, “Classes of structures with universe a subset of 1”, Journal of Logic and Computation, 23:6 (2013), 1249
Uri Andrews, “The degrees of categorical theories with recursive models”, Proc. Amer. Math. Soc., 141:7 (2013), 2501
Montalban A., “Rice Sequences of Relations”, Philos. Trans. R. Soc. A-Math. Phys. Eng. Sci., 370:1971, SI (2012), 3464–3487
Michael Rathjen, “2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10”, Bull. symb. log, 17:2 (2011), 272
Stefan Vatev, Lecture Notes in Computer Science, 6735, Models of Computation in Context, 2011, 300
Fokina E.B., Kalimullin I., Miller R., “Degrees of categoricity of computable structures”, Arch. Math. Logic, 49:1 (2010), 51–67
Khoussainov B., Montalban A., “A Computable N-0-Categorical Structure Whose Theory Computes True Arithmetic”, Journal of Symbolic Logic, 75:2 (2010), 728–740
Fokina E.B., “Index sets for some classes of structures”, Ann. Pure Appl. Logic, 157:2-3 (2009), 139–147
Soskova A., Soskov I.N., “A jump inversion theorem for the degree spectra”, J. Logic Comput., 19:1 (2009), 199–215

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

Statistics & downloads:
Abstract page:	636
Full-text PDF :	165
References:	84
First page:	1

Что такое QR-код?

Registration to the website

Logotypes