Geodesic
Computing and dominating the Ryll-Nardzewski function
Algebra i logika, Tome 53 (2014) no. 2, pp. 271-281.

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

For a countably categorical theory $\mathrm T$, we study the complexity of computing and the complexity of dominating the function specifying the number of $n$-types consistent with $\mathrm T$.
Keywords: countably categorical theory, Ryll-Nardzewski function, complexity of function. 
@article{AL_2014_53_2_a7,
     author = {U. Andrews and A. M. Kach},
     title = {Computing and dominating the {Ryll-Nardzewski} function},
     journal = {Algebra i logika},
     pages = {271--281},
     publisher = {mathdoc},
     volume = {53},
     number = {2},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2014_53_2_a7/}
}
TY  - JOUR
AU  - U. Andrews
AU  - A. M. Kach
TI  - Computing and dominating the Ryll-Nardzewski function
JO  - Algebra i logika
PY  - 2014
SP  - 271
EP  - 281
VL  - 53
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2014_53_2_a7/
LA  - ru
ID  - AL_2014_53_2_a7
ER  - 
%0 Journal Article
%A U. Andrews
%A A. M. Kach
%T Computing and dominating the Ryll-Nardzewski function
%J Algebra i logika
%D 2014
%P 271-281
%V 53
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2014_53_2_a7/
%G ru
%F AL_2014_53_2_a7
U. Andrews; A. M. Kach. Computing and dominating the Ryll-Nardzewski function. Algebra i logika, Tome 53 (2014) no. 2, pp. 271-281. http://geodesic.mathdoc.fr/item/AL_2014_53_2_a7/

[1] E. Engeler, “Äquivalenzklassen von $n$-Tupeln”, Z. Math. Logik Grundlagen Math., 5 (1959), 340–345 | DOI | MR | Zbl

[2] C. Ryll-Nardzewski, “On the categoricity on power $\le\aleph_0$”, Bull. Acad. Pol. Sci. Sér. Sci. Math. Astron. Phys., 7 (1959), 545–548 | MR | Zbl

[3] L. Svenonius, “$\aleph_0$-categoricity in first-order predicate calculus”, Theoria (Lund), 25 (1959), 82–94 | DOI | MR

[4] J. H. Schmerl, “A decidable $\aleph_0$-categorical theory with a non-recursive Ryll-Nardzewski function”, Fundam. Math., 98:2 (1978), 121–125 | MR | Zbl

[5] B. Khoussainov, A. Montal'an, “A computable $\aleph_0$-categorical structure whose theory computes true arithmetic”, J. Symb. Log., 75:2 (2010), 728–740 | DOI | MR | Zbl

[6] U. Andrews, “The degrees of categorical theories with recursive models”, Proc. Am. Math. Soc., 141:7 (2013), 2501–2514 | DOI | MR | Zbl

[7] W. Hodges, A shorter model theory, Cambridge Univ. Press, Cambridge, 1997 | MR

[8] C. J. Ash, J. F. Knight, Computable structures and the hyperarithmetical hierarchy, Stud. Logic Found. Math., 144, Elsevier Sci. B.V., Amsterdam etc., 2000 | MR | Zbl

[9] C. G. Jockusch (Jr.), T. G. McLaughlin, “Countable retracing functions and $\Pi^0_2$ predicates”, Pac. J. Math., 30 (1969), 67–93 | DOI | MR | Zbl

[10] L. A. Rogers, “Ulm's theorem for partially ordered structures related to simply presented Abelian $p$-groups”, Trans. Am. Math. Soc., 227 (1977), 333–343 | MR | Zbl

[11] A. V. Kuznetsov, B. A. Trakhtenbrot, “Issledovanie chastichno rekursivnykh operatorov sredstvami teorii berovskogo prostranstva”, DAN SSSR, 105:5 (1955), 897–900 | Zbl

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