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

Présenté par : Yves Meyer

Delhommé, Christian1
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, Tome 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
Delhommé, Christian 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 = {Delhomm\'e, Christian},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2004.03.035/}
}
TY  - JOUR
AU  - Delhommé, Christian
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2004.03.035/
DO  - 10.1016/j.crma.2004.03.035
LA  - fr
ID  - CRMATH_2004__339_1_5_0
ER  - 
%0 Journal Article
%A Delhommé, Christian
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2004.03.035/
%R 10.1016/j.crma.2004.03.035
%G fr
%F CRMATH_2004__339_1_5_0
Delhommé, Christian. Automaticité des ordinaux et des graphes homogènes. Comptes Rendus. Mathématique, Tome 339 (2004) no. 1, pp. 5-10. doi : 10.1016/j.crma.2004.03.035. http://www.numdam.org/articles/10.1016/j.crma.2004.03.035/

[1] Abraham, U.; Bonnet, R. 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] Blumensath, A.; Graedel, E. Automatic structures, LICS'00, 2000, pp. 51-62

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

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

[6] Dauchet, M.; Tison, S. 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] Fraı̈ssé, R. Theory of relations, Stud. Logic, vol. 118, North-Holland, 1986

[11] Frougny, C.; Sakarovitch, J. 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] Hodgson, B.R. Décidabilité par automate fini, Ann. Sci. Math. Québec, Volume 7 (1983) no. 1, pp. 39-57

[14] Khoussainov, B.; Nerode, A. 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 :