Estimation of the algorithmic complexity of classes of computable models

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

doi:10.1007/s11202-008-0049-1

Estimation of the algorithmic complexity of classes of computable models

Переведенное название: Оценка алгоритмической сложности классов вычислимых моделей

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

Результат исследования: Научные публикации в периодических изданиях › статья

6 Цитирования (Scopus)

Аннотация

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)).

Переведенное название	Оценка алгоритмической сложности классов вычислимых моделей
Язык оригинала	английский
Страницы (с-по)	512-523
Число страниц	12
Журнал	Siberian Mathematical Journal
Том	49
Номер выпуска	3
DOI	https://doi.org/10.1007/s11202-008-0049-1
Состояние	Опубликовано - мая 2008

Доступ к документу

10.1007/s11202-008-0049-1

Цитировать

Павловский, Е. Н. (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

@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",

}

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 -