Geodesic
On automatic and decidable linear orderings
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 100-110.

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

Let $\EuScript A$ be the class of automatic linear orderings, $\EuScript{AA}$ be the class of linear orderings which are computably categorical in the class of automatic presentation, $\EuScript{AD}$ be the class of linear orderings which are computably categorical in the class of decidable presentations. Obviously, $\EuScript{AD}\cap\EuScript A\subset\EuScript{AD}$. Since all automatic structures are decidable, $\EuScript{AD}\cap\EuScript A\subset\EuScript{AA}$, and one can easily see that $\EuScript{AD}\cap\EuScript A$ is nonempty. We show that there exist a linear order $\mathcal L_1\in\EuScript{AA}$ such that $\mathcal L_1\notin\EuScript{AD}$ and a linear order $\mathcal L_2\in\EuScript{AD}$ such that $\mathcal L_2\notin\EuScript A$. By this, the inclusions $\EuScript{AD}\cap\EuScript A\subset\EuScript{AD}$ and $\EuScript{AD}\cap\EuScript A\subset\EuScript{AA}$ are proper. In addition, we construct an example of a non–automatic linear order which is decidable in the language with the additional quantifier $\exists^\infty$.
Keywords: automatic structure, decidable structure, linear ordering, computable categoricity. 
@article{SEMR_2010_7_a8,
     author = {A. A. Gavryushkina},
     title = {On automatic and decidable linear orderings},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {100--110},
     publisher = {mathdoc},
     volume = {7},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2010_7_a8/}
}
TY  - JOUR
AU  - A. A. Gavryushkina
TI  - On automatic and decidable linear orderings
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2010
SP  - 100
EP  - 110
VL  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2010_7_a8/
LA  - ru
ID  - SEMR_2010_7_a8
ER  - 
%0 Journal Article
%A A. A. Gavryushkina
%T On automatic and decidable linear orderings
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2010
%P 100-110
%V 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2010_7_a8/
%G ru
%F SEMR_2010_7_a8
A. A. Gavryushkina. On automatic and decidable linear orderings. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 100-110. http://geodesic.mathdoc.fr/item/SEMR_2010_7_a8/

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

[2] S. S. Goncharov, “Silnaya konstruktiviziruemost odnorodnykh modelei”, Algebra i logika, 17:4 (1978), 363–388 | MR | Zbl

[3] G. Keisler, Ch. Ch. Chen, Teoriya modelei, Mir, Moskva, 1977 | MR

[4] A. T. Nurtazin, “Silnye i slabye konstruktivizatsii i vychislimye semeistva”, Algebra i logika, 13:3 (1974), 311–323 | MR | Zbl

[5] A. A. Revenko, “Avtoustoichivost avtomatnykh predstavlenii ordinalov i lineinykh poryadkov nizkogo ranga”, Vestnik NGU, seriya Matematika, 8:4 (2008), 76–88

[6] M. G. Peretyatkin, “Kriterii silnoi konstruktiviziruemosti odnorodnoi modeli”, Algebra i logika, 17:4 (1978), 436–454 | MR

[7] C. J. Ash, J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, 144, Elsevier, 2000 | MR | Zbl

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

[9] A. Blumensath, E. Grädel, “Finite presentations of infinite structures: Automata and Interpretations”, Theory of Computing Systems, 37 (2004), 641–674 | DOI | MR | Zbl

[10] C. Delhomme, Non-automaticity of $\omega^\omega$, manuscript, 2001 | Zbl

[11] R. G. Downey, “Computability Theory and Linear Orderings”, Handbook of Recursive Mathematics, chapter 14, v. 2, Studies in Logic and the Foundations of Mathematics, 139, Elsevier, 1998, 823–976 | MR | Zbl

[12] S. S. Goncharov, “Autostable Models and Algorithmic Dimentions”, Handbook of Recursive Mathematics, chapter 6, v. 1, Studies in Logic and the Foundations of Mathematics, 138, Elsevier, 1998, 261–287 | MR | Zbl

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

[14] B. Khoussainov, M. Minnes and J. Liu, “Unary Automatic Graph”, Mathematical Structures in Computer Sciens, 19:1 (2008), 533–152 | MR

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

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

[17] B. Khoussainov, S. Rubin, F. Stephan, “Automatic Linear Orders and Trees”, ACM Transactions on Computational Logic, 6:4 (2005), 675–700 | DOI | MR

[18] C. H. Langford, “Theorems on Deducibility”, Annals of Mathematics, 28:2 (1927), 459–471 | MR | Zbl

[19] M. Minnes, Computability and complexity properties of automatic structures and their applications, PhD Thesis, Cornell University, 2008 | MR

[20] M. Moses, Recursive Properties of Isomorphism Types, PhD Thesis, Monash University, Clayton, Victoria, Australia, 1983

[21] M. Moses, “Recursive Linear Orderings with Recursive Successivities”, Annals of Pure and Appleing Logic, 27 (1984), 253–264 | DOI | MR | Zbl

[22] J. B. Remmel, “Recursively Categorical Linear Orderings”, Proceedings of American Mathematical Society, 83 (1981), 387–391 | MR | Zbl

[23] J. G. Rosenstein, Linear Orderings, Academic Press, 1982 | MR | Zbl

[24] S. Rubin, Automatic Structures, PhD Thesis, The University of Auckland, New Zealand, 2004

[25] S. Rubin, “Survey of automatic structures”, The Bulletin of Symbolic Logic, 14:2 (2008), 169–200 | DOI | MR