Standard

Estimation of the algorithmic complexity of classes of computable models. / Павловский, Евгений Николаевич.

In: Siberian Mathematical Journal, Vol. 49, No. 3, 05.2008, p. 512-523.

Research output: Contribution to journal › Article › peer-review

Harvard

Павловский, ЕН 2008, 'Estimation of the algorithmic complexity of classes of computable models', Siberian Mathematical Journal, vol. 49, no. 3, pp. 512-523. https://doi.org/10.1007/s11202-008-0049-1

APA

Павловский, Е. Н. (2008). Estimation of the algorithmic complexity of classes of computable models. Siberian Mathematical Journal, 49(3), 512-523. https://doi.org/10.1007/s11202-008-0049-1

Vancouver

Павловский ЕН. Estimation of the algorithmic complexity of classes of computable models. Siberian Mathematical Journal. 2008 May;49(3):512-523. doi: 10.1007/s11202-008-0049-1

Author

Павловский, Евгений Николаевич. / Estimation of the algorithmic complexity of classes of computable models. In: Siberian Mathematical Journal. 2008 ; Vol. 49, No. 3. pp. 512-523.

BibTeX

@article{3e5415674b754a46a63907a29a3c0ffd,
title = "Estimation of the algorithmic complexity of classes of computable models",
abstract = "We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models (Sigma(0)(2)-complete), computable models with omega-categorical theories (Delta(0)(omega)-complex Pi(0)(omega+2)-set), prime models (Delta(0)(omega)-complex Pi(0)(omega+2)-set), models with omega(1)-categorical theories (Delta(0)(omega)-complex Sigma(0)(omega+1)-set). We obtain a universal lower bound for the model-theoretic properties preserved by Marker's extensions (Delta(0)(omega)).",
keywords = "computable model, index set",
author = "Павловский, {Евгений Николаевич}",
year = "2008",
month = may,
doi = "10.1007/s11202-008-0049-1",
language = "English",
volume = "49",
pages = "512--523",
journal = "Siberian Mathematical Journal",
issn = "0037-4466",
publisher = "MAIK NAUKA/INTERPERIODICA/SPRINGER",
number = "3",

}

RIS

TY - JOUR

T1 - Estimation of the algorithmic complexity of classes of computable models

AU - Павловский, Евгений Николаевич

PY - 2008/5

Y1 - 2008/5

N2 - We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models (Sigma(0)(2)-complete), computable models with omega-categorical theories (Delta(0)(omega)-complex Pi(0)(omega+2)-set), prime models (Delta(0)(omega)-complex Pi(0)(omega+2)-set), models with omega(1)-categorical theories (Delta(0)(omega)-complex Sigma(0)(omega+1)-set). We obtain a universal lower bound for the model-theoretic properties preserved by Marker's extensions (Delta(0)(omega)).

AB - We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models (Sigma(0)(2)-complete), computable models with omega-categorical theories (Delta(0)(omega)-complex Pi(0)(omega+2)-set), prime models (Delta(0)(omega)-complex Pi(0)(omega+2)-set), models with omega(1)-categorical theories (Delta(0)(omega)-complex Sigma(0)(omega+1)-set). We obtain a universal lower bound for the model-theoretic properties preserved by Marker's extensions (Delta(0)(omega)).

KW - computable model

KW - index set

U2 - 10.1007/s11202-008-0049-1

DO - 10.1007/s11202-008-0049-1

M3 - Article

VL - 49

SP - 512

EP - 523

JO - Siberian Mathematical Journal

JF - Siberian Mathematical Journal

SN - 0037-4466

IS - 3

ER -

ID: 18919714