Geodesic
Scott Rank of Automatic Partial Orderings
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 10 (2010) no. 2, pp. 37-44 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

One of the main problems in the theory of automatic structures is the problem of characterization of automatic structures and subclasses of automatic structures. Scott ranks measure the complexity of the description of the isomorphism types of structures. M. Minnes and B. Khoussainov showed that for every ordinal $\alpha$ at most $\omega_1^{CK}+1$ there exists an automatic structure of Scott rank $\alpha$ [7;8]. In this paper we show that the same result holds for automatic partial orders.
Keywords: automatic structure, partial order, Scott rank. 
@article{VNGU_2010_10_2_a2,
     author = {A. A. Gavryushkina},
     title = {Scott {Rank} of {Automatic} {Partial} {Orderings}},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {37--44},
     year = {2010},
     volume = {10},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2010_10_2_a2/}
}
TY  - JOUR
AU  - A. A. Gavryushkina
TI  - Scott Rank of Automatic Partial Orderings
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2010
SP  - 37
EP  - 44
VL  - 10
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VNGU_2010_10_2_a2/
LA  - ru
ID  - VNGU_2010_10_2_a2
ER  - 
%0 Journal Article
%A A. A. Gavryushkina
%T Scott Rank of Automatic Partial Orderings
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2010
%P 37-44
%V 10
%N 2
%U http://geodesic.mathdoc.fr/item/VNGU_2010_10_2_a2/
%G ru
%F VNGU_2010_10_2_a2
A. A. Gavryushkina. Scott Rank of Automatic Partial Orderings. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 10 (2010) no. 2, pp. 37-44. http://geodesic.mathdoc.fr/item/VNGU_2010_10_2_a2/

[1] C. J. Ash, J. F. Knight (eds.), Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, 144, North-Holland Publishing Co., Amsterdam, 2000 | MR

[2] Barany V., Automatic Presentations of Infinite Structures, PhD Thesis, RWTH Aachen, 2007

[3] Blumensath A., Automatic Structures, Diploma thesis, RWTH Aachen, 1999

[4] Blumensath A., Gradel E., “Automatic structures”, $15^\text{th}$ Symposium on Logic in Computer Science (LICS), 2000, 51–62 | MR

[5] Goncharov S. S., “Isomorphism and Definable Relations on Computable Models”, Logic Colloquium'05, Lecture Notes in Logic, 28, 2006, 26–45 | MR

[6] Hodgson B. R., Theories Decidables par Automate Fini, PhD Thesis, University of Montreal, 1976 | MR

[7] Khoussainov B., Minnes M., “Model Theoretic Complexity of Automatic Structures”, TAMC 2008, Lecture Notes in Computer Science, 4978, 514–525 | DOI | MR | Zbl

[8] Khoussainov B., Minnes M., “Model Theoretic Complexity of Automatic Structures”, Annals of Pure and Applied Logic, 161 (2009), 416–426 | DOI | MR | Zbl

[9] Khoussainov B., Nerode A., “Automatic Presentations of Structures”, Lecture Notes in Computer Science, 960, 1995, 367–392 | DOI | MR

[10] Khoussainov B., Nerode A., “Open Questions in the Theory of Automatic Structures”, Bulleten of EATCS, 94 (2008), 181–204 | MR | Zbl

[11] Khoussainov B., Nies A., Rubin S., Stephan F., “Automatic Structures: Richness and Limitations”, Logical Methods in Computer Science, 3:2 (2007), 1–18 | DOI | MR

[12] Kuske D., Lohrey M., “Automatic Structures of Bounded Degree Revisited”, CSL, Lecture Notes in Computer Science, 5771, 2009, 364–378 | DOI | MR | Zbl

[13] Kuske D., Liu J., Lohrey M., The Isomorphism Problem On Classes of Automatic Structures, manuscript

[14] Minnes M., Computability and Complexity Properties of Automatic Structures and their Applications, PhD Thesis, Cornell University, 2008 | MR

[15] Rubin S., “Automata Presenting Structures: A Survey of the Finite String Case”, The Bulletin of Symbolic Logic, 14:2 (2008), 169–200 | DOI | MR