Geodesic
Complexity of Ehrenfeucht models
Algebra i logika, Tome 45 (2006) no. 5, pp. 507-519.

Voir la notice de l'article provenant de la source Math-Net.Ru

We look at examples of Ehrenfeucht theories possessing constructive models and countable models of different complexities, and estimate complexity of the Ehrenfeucht theories having constructive models.
Keywords: Ehrenfeucht theory, constructive model. 
@article{AL_2006_45_5_a0,
     author = {A. N. Gavryushkin},
     title = {Complexity of {Ehrenfeucht} models},
     journal = {Algebra i logika},
     pages = {507--519},
     publisher = {mathdoc},
     volume = {45},
     number = {5},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2006_45_5_a0/}
}
TY  - JOUR
AU  - A. N. Gavryushkin
TI  - Complexity of Ehrenfeucht models
JO  - Algebra i logika
PY  - 2006
SP  - 507
EP  - 519
VL  - 45
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2006_45_5_a0/
LA  - ru
ID  - AL_2006_45_5_a0
ER  - 
%0 Journal Article
%A A. N. Gavryushkin
%T Complexity of Ehrenfeucht models
%J Algebra i logika
%D 2006
%P 507-519
%V 45
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2006_45_5_a0/
%G ru
%F AL_2006_45_5_a0
A. N. Gavryushkin. Complexity of Ehrenfeucht models. Algebra i logika, Tome 45 (2006) no. 5, pp. 507-519. http://geodesic.mathdoc.fr/item/AL_2006_45_5_a0/

[1] B. Hart, E. Hrushovski, M. S. Laskowski, “The uncountable spectra of countable theories”, Ann. Math. (2), 152:1 (2000), 207–257 | DOI | MR | Zbl

[2] M. Lerman, J. Schmerl, “Theories with recursive models”, J. Symb. Log., 44:1 (1979), 59–76 | DOI | MR | Zbl

[3] J. Knight, “Nonarithmetical $\aleph_0$-categorical theories with recursive models”, J. Symb. Log., 59:1 (1994), 106–112 | DOI | MR | Zbl

[4] S. S. Goncharov, B. Khusainov, “O slozhnosti teorii vychislimykh $\aleph_1$-kategorichnykh modelei”, Vestnik NGU, ser.: matem., mekh. inform., 1:2 (2001), 63–76 | Zbl

[5] S. S. Goncharov, B. Khusainov, “Slozhnost teorii vychislimykh kategorichnykh modelei”, Algebra i logika, 43:6 (2004), 650–665 | MR | Zbl

[6] C. C. Chang, H. J. Keisler, Model theory, North-Holland, Amsterdam, 1990 ; G. Keisler, Ch. Ch. Chen, Teoriya modelei, Mir, M., 1973 | MR

[7] C. C. Goncharov, Yu. L. Ershov, Konstruktivnye modeli, Sibirskaya shkola algebry i logiki, Nauch. kniga (NII MIOO NGU), Novosibirsk, 1999

[8] H. J. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, New York–Toronto–London, 1967 ; Kh. Dzh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR | Zbl | MR

[9] R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Springer-Verlag, Berlin–New York, 1987 ; R. I. Soar, Vychislimo perechislimye mnozhestva i stepeni. Izuchenie vychislimykh funktsii i vychislimo perechislimykh mnozhestv, Kazanskoe matem. ob-vo, Kazan, 2000 | MR | MR | Zbl

[10] R. L. Vaught, “Denumerable models of complete theories”, Infinistic methods, Proc. symp. found. math., Warshaw, 1959, 303–321 (1961) | MR

[11] M. G. Peretyatkin, “O polnykh teoriyakh s konechnym chislom schetnykh modelei”, Algebra i logika, 12:5 (1973), 550–576

[12] R. Reed, “A decidable Ehrenfeucht theory with exactly two hyperarithmetic models”, Ann. Pure Appl. Logic, 53:2 (1991), 135–168 | DOI | MR | Zbl