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/