Geodesic
Complexity of Ehrenfeucht models
Algebra i logika, Tome 45 (2006) no. 5, pp. 507-519
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2006},
     volume = {45},
     number = {5},
     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
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
%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