Geodesic
Index sets of classes in automatic structures
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 3 (2006), pp. 153-154 
N. S. Vinokurov. Index sets of classes in automatic structures. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 3 (2006), pp. 153-154. http://geodesic.mathdoc.fr/item/SEMR_2006_3_a37/
@article{SEMR_2006_3_a37,
     author = {N. S. Vinokurov},
     title = {Index sets of classes in automatic structures},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {153--154},
     year = {2006},
     volume = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2006_3_a37/}
}
TY  - JOUR
AU  - N. S. Vinokurov
TI  - Index sets of classes in automatic structures
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2006
SP  - 153
EP  - 154
VL  - 3
UR  - http://geodesic.mathdoc.fr/item/SEMR_2006_3_a37/
LA  - ru
ID  - SEMR_2006_3_a37
ER  - 
%0 Journal Article
%A N. S. Vinokurov
%T Index sets of classes in automatic structures
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2006
%P 153-154
%V 3
%U http://geodesic.mathdoc.fr/item/SEMR_2006_3_a37/
%G ru
%F SEMR_2006_3_a37

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

We find levels of index sets in arithmetical and analytical hierarchies for some classes of automatic structures.

[1] B. Khoussainov, A. Nerode, “Automatic presentations of structures”, Lecture Notes in Computer Science, 960, 1995, 367–392 | MR

[2] B. Khoussainov, A. Nies, S. Rubin, F. Stephan, “Automatic structures: richness and limitations”, Proc. 19th IEEE Symp. on Logic in Computer Science (2004, Turku, Finland), 44–53 | MR

[3] B. Khoussainov, S. Rubin, H. Ishihara, “On isomorphism invariants of some automatic structures”, Proc. 17th IEEE Symp. on Logic in Computer Science (2002, Copenhagen, Denmark), 43–53

[4] S. Rubin, Automata structures, PhD Thesis, University of Auckland, 2004 http://www.cs.auckland.ac.nz/~bmk/Sasha/SashaPhDthesis.pdf