|
This article is cited in 1 scientific paper (total in 1 paper)
Constructive and Non-Constructive Infinite Formulas in Computable Structures
P. E. Alaev Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Abstract:
A transition from arbitrary $L_{\omega_1\omega}$-formulas to computable formulas in the class of computable structures is considered. It is shown that transition of a certain type is possible which doubles the complexity of the formulas. In addition, the complexity jump is analyzed for the transition from an arbitrary Scott family consisting of $L_{\omega_1\omega}$-formulas to a computable Scott family in a fixed computable structure. Exact estimates of this jump are found.
Keywords:
computable structure, computable formula, Scott family.
Received: 27.04.2001 Revised: 01.08.2002
Citation:
P. E. Alaev, “Constructive and Non-Constructive Infinite Formulas in Computable Structures”, Algebra Logika, 42:4 (2003), 391–412; Algebra and Logic, 42:4 (2003), 219–231
Linking options:
https://www.mathnet.ru/eng/al37 https://www.mathnet.ru/eng/al/v42/i4/p391
|
Statistics & downloads: |
Abstract page: | 314 | Full-text PDF : | 116 | References: | 33 | First page: | 1 |
|