HAL : hal-00695443, version 1

arXiv : 1205.1775

Fiche détaillée

Récupérer au format BibTeX - EndNote - TEI - RefWorks -

International Journal of Unconventional Computing 9, 1-2 (2013) 61-70

Automatic Ordinals

Olivier Finkel 1, 2, Stevo Todorcevic 1, 2, 3

(2013)

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.

1 :	Équipe de Logique Mathématique (ELM)
	CNRS : UMR7056 – Université Paris VII - Paris Diderot
2 :	Institut de Mathématiques de Jussieu (IMJ)
	CNRS : UMR7586 – Université Pierre et Marie Curie [UPMC] - Paris VI – Université Paris VII - Paris Diderot
3 :	Department of Mathematics - University of Toronto
	University of Toronto

Domaine

:

Mathématiques/Logique Informatique/Logique en informatique

Mots Clés : $\omega$-tree-automatic structures – $\omega^n$-automatic structures – ordinals.

hal-00695443, version 1

http://hal.archives-ouvertes.fr/hal-00695443

oai:hal.archives-ouvertes.fr:hal-00695443

Contributeur : Olivier Finkel <>

Soumis le : Mardi 8 Mai 2012, 15:34:09

Dernière modification le : Mardi 9 Avril 2013, 16:33:37