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
СостояниеОпубликовано - мая 2008

Цитировать