|
Sibirskii Matematicheskii Zhurnal, 2008, Volume 49, Number 3, Pages 635–649
(Mi smj1867)
|
|
|
|
This article is cited in 12 scientific papers (total in 12 papers)
Estimation of the algorithmic complexity of classes of computable models
E. N. Pavlovskii Novosibirsk State University, Mechanics and Mathematics Department
Abstract:
We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models ($\Sigma_2^0$-complete), computable models with $\omega$-categorical theories ($\Delta_\omega^0$-complex $\Pi_{\omega+2}^0$-set), prime models ($\Delta_\omega^0$-complex $\Pi_{\omega+2}^0$-set), models with $\omega_1$-categorical theories ($\Delta_\omega^0$-complex $\Sigma_{\omega+1}^0$-set). We obtain a universal lower bound for the model-theoretic properties preserved by Marker's extensions ($\Delta_\omega^0$).
Keywords:
computable model, index set.
Received: 14.06.2007 Revised: 04.04.2008
Citation:
E. N. Pavlovskii, “Estimation of the algorithmic complexity of classes of computable models”, Sibirsk. Mat. Zh., 49:3 (2008), 635–649; Siberian Math. J., 49:3 (2008), 512–523
Linking options:
https://www.mathnet.ru/eng/smj1867 https://www.mathnet.ru/eng/smj/v49/i3/p635
|
Statistics & downloads: |
Abstract page: | 355 | Full-text PDF : | 111 | References: | 53 | First page: | 2 |
|