Comptes Rendus
no. 1
Combinatoire
Automaticité des ordinaux et des graphes homogènes

Présenté par : Yves Meyer

Christian Delhommé1
1 ERMIT, département de mathématiques, université de La Réunion, 15, avenue René Cassin, BP 7151, 97715 Saint-Denis Messag cedex 9, La Réunion, France
Comptes Rendus. Mathématique, Volume 339 (2004) no. 1, pp. 5-10.

Les structures automatiques (resp. arbre-automatiques) sont les structures relationnelles dont le domaine est un ensemble régulier de mots (resp. de termes) finis et dont chaque relation atomique est reconnaissable par un automate multi-bandes synchrones. Nous établissons des critères d'automaticité et énonçons des critères analogues d'arbre-automaticité, dont il découle en particulier, d'une part que le graphe aléatoire n'est pas automatique, ni même arbre-automatique, et d'autre part, que tout ordre bien fondé automatique est de hauteur strictement inférieure à ωω, et que ωωω est l'ensemble des ordinaux arbre-automatiques.

We establish criteria of automaticity and we state analogous criteria of tree-automaticity which show, on the one-hand that the random graph is neither automatic nor tree-automatic, and on the other hand that every well-founded automatic poset has height less than ωω and that ωωω is the set of tree-automatic ordinals.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2004.03.035
Christian Delhommé 1

1 ERMIT, département de mathématiques, université de La Réunion, 15, avenue René Cassin, BP 7151, 97715 Saint-Denis Messag cedex 9, La Réunion, France 
@article{CRMATH_2004__339_1_5_0,
     author = {Christian Delhomm\'e},
     title = {Automaticit\'e des ordinaux et des graphes homog\`enes},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {5--10},
     publisher = {Elsevier},
     volume = {339},
     number = {1},
     year = {2004},
     doi = {10.1016/j.crma.2004.03.035},
     language = {fr},
}
TY  - JOUR
AU  - Christian Delhommé
TI  - Automaticité des ordinaux et des graphes homogènes
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 5
EP  - 10
VL  - 339
IS  - 1
PB  - Elsevier
DO  - 10.1016/j.crma.2004.03.035
LA  - fr
ID  - CRMATH_2004__339_1_5_0
ER  - 
%0 Journal Article
%A Christian Delhommé
%T Automaticité des ordinaux et des graphes homogènes
%J Comptes Rendus. Mathématique
%D 2004
%P 5-10
%V 339
%N 1
%I Elsevier
%R 10.1016/j.crma.2004.03.035
%G fr
%F CRMATH_2004__339_1_5_0
Christian Delhommé. Automaticité des ordinaux et des graphes homogènes. Comptes Rendus. Mathématique, Volume 339 (2004) no. 1, pp. 5-10. doi : 10.1016/j.crma.2004.03.035. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2004.03.035/

[1] U. Abraham; R. Bonnet Hausdorff's theorem for posets that satisfy the finite antichain property, Fund. Math., Volume 159 (1999) no. 1, pp. 51-69

[2] A. Blumensath, Automatic Structures, Diploma Thesis, RWTH, University of Aachen, 1999

[3] A. Blumensath; E. Graedel Automatic structures, LICS'00, 2000, pp. 51-62

[4] P.W. Carruth Arithmetic of ordinals with applications to the theory of ordered Abelian groups, Bull. Amer. Math. Soc., Volume 48 (1942), pp. 262-271

[5] H. Common; M. Dauchet; R. Gilleron; D. Lugiez; S. Tison; M. Tomassi TATA: Tree Automata and Their Applications http://l3ux02.univ-lille3.fr/tata/

[6] M. Dauchet; S. Tison The theory of ground rewrite systems is decidable, LICS'90, IEEE, 1990, pp. 242-248

[7] C. Delhommé, Rado's graph is not automatic, Manuscript, 2001

[8] C. Delhommé, Non automaticity of ωω, Manuscript, 2001

[9] C. Delhommé, V. Goranko, T. Knapik, Automatic linear orderings, Manuscript, 2002

[10] R. Fraı̈ssé Theory of relations, Stud. Logic, vol. 118, North-Holland, 1986

[11] C. Frougny; J. Sakarovitch Synchronized rational relations of finite and infinite words, Theoret. Comput. Sci., Volume 108 (1993), pp. 45-82

[12] B.R. Hodgson, Théories décidables par automate fini, Thèse de doctorat, Université de Montréal, 1976, 171 p

[13] B.R. Hodgson Décidabilité par automate fini, Ann. Sci. Math. Québec, Volume 7 (1983) no. 1, pp. 39-57

[14] B. Khoussainov; A. Nerode Automatic presentations of structures, Logic and Comput. Complex., Lecture Notes in Comput. Sci., vol. 960, 1995, pp. 367-392

[15] B. Khoussainov, S. Rubin, F. Stephan, On automatic partial orders, Manuscript, 2003

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Sur la complexité des nombres algébriques

Boris Adamczewski; Yann Bugeaud; Florian Luca

C. R. Math (2004)

Ensembles reconnaissables de séries formelles sur un corps fini

Luc Bélair; Maxime Gélinas; Françoise Point

C. R. Math (2016)