Geodesic
Autostability of Automatic Presentations of Well Orders and Low Rank Linear Orders
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 8 (2008) no. 4, pp. 78-88 
A. A. Revenko. Autostability of Automatic Presentations of Well Orders and Low Rank Linear Orders. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 8 (2008) no. 4, pp. 78-88. http://geodesic.mathdoc.fr/item/VNGU_2008_8_4_a7/
@article{VNGU_2008_8_4_a7,
     author = {A. A. Revenko},
     title = {Autostability of {Automatic} {Presentations} of {Well} {Orders} and {Low} {Rank} {Linear} {Orders}},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {78--88},
     year = {2008},
     volume = {8},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2008_8_4_a7/}
}
TY  - JOUR
AU  - A. A. Revenko
TI  - Autostability of Automatic Presentations of Well Orders and Low Rank Linear Orders
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2008
SP  - 78
EP  - 88
VL  - 8
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VNGU_2008_8_4_a7/
LA  - ru
ID  - VNGU_2008_8_4_a7
ER  - 
%0 Journal Article
%A A. A. Revenko
%T Autostability of Automatic Presentations of Well Orders and Low Rank Linear Orders
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2008
%P 78-88
%V 8
%N 4
%U http://geodesic.mathdoc.fr/item/VNGU_2008_8_4_a7/
%G ru
%F VNGU_2008_8_4_a7

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

The proposition that if $L$ is linear order then its $FC$-rank is finite was proved in Rubin's thesis (S. Rubin, Automatic Structures, A thesis submitted in partial fulfilment of the requirements for the Degree of Doctor of Philosophy, The University of Auckland, 2004), Automatic Structures. We showed that every two automatic presentation of ordinal or linear order with $FC$-rank less then 2 are computable isomorphic. The example of automatic linear order with complicated structure was provided. Moreover it was showed that every automatic linear order is definable in appropriate automatic linear order with $FC$-rank 1 by the first order fomula with additional quantifier $\exists^\infty$.

[1] Goncharov S. S., Ershov Yu. L., Konstruktivnye modeli, Nauchnaya kniga, Novosibirsk, 1999

[2] Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972

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

[4] Delhomme C., Non-automaticity of $\omega^\omega$, Manuscript, 2001

[5] Delhomme C., Goranko V., Knapik T., Automatic Linear Orderings, 2003

[6] Hodgson B. R., Théories décidables par automate fini, Phd. thesis, University of Montréal, 1976

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

[8] Khoussainov B., Rubin S., Stephan F., Automatic Linear Orders and Trees, CDMTCS Technical Report 208, Department of Computer Science, University of Auckland, 2003

[9] Rosenstein J. G., Linear Orderings, Academic Press, N.Y., 1982

[10] Rubin S., Automatic Structures, A Thesis Submitted in Partial Fulfilment of the Requirements for the Degree of Doctor of Philosophy, The University of Auckland, 2004

[11] Rubin S., “Finite Automata and Well Ordered Sets”, New Zealand Journal of Computing, 7:2 (1999), 39–46