Automatic Ordinals - Logique
Article Dans Une Revue International Journal of Unconventional Computing Année : 2013

Automatic Ordinals

Résumé

We prove that the injectively omega-tree-automatic ordinals are the ordinals smaller than $\omega^{\omega^\omega}$. Then we show that the injectively $\omega^n$-automatic ordinals, where $n>0$ is an integer, are the ordinals smaller than $\omega^{\omega^n}$. This strengthens a recent result of Schlicht and Stephan who considered in [Schlicht-Stephan11] the subclasses of finite word $\omega^n$-automatic ordinals. As a by-product we obtain that the hierarchy of injectively $\omega^n$-automatic structures, n>0, which was considered in [Finkel-Todorcevic12], is strict.
Fichier principal
Vignette du fichier
Automatic-Ordinals.pdf (122.17 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00695443 , version 1 (08-05-2012)

Identifiants

Citer

Olivier Finkel, Stevo Todorcevic. Automatic Ordinals. International Journal of Unconventional Computing, 2013, 9 (1-2), pp.61-70. ⟨hal-00695443⟩
163 Consultations
144 Téléchargements

Altmetric

Partager

More