Automaticity of ordinals and of homogeneous graphs.

被引：42
作者：
Delhommé, C [1 ]
机构：
[1] Univ Reunion, Dept Math, ERMIT, 15 Ave Rene Cassin,BP 7151, F-97715 St Denis Messageries 9, Reunion, France
来源：
COMPTES RENDUS MATHEMATIQUE | 2004年 / 339卷 / 01期
关键词：
D O I：
10.1016/j.crma.2004.03.035
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Automaticity of ordinals and of homogeneous graphs. 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 omega(omega) and that (omega)omega(omega) is the set of tree-automatic ordinals.
引用
收藏
页码：5 / 10
页数：6
相关论文
共 15 条
  • [1] Hausdorff's theorem for posets that satisfy the finite antichain property
    Abraham, U
    Bonnet, R
    [J]. FUNDAMENTA MATHEMATICAE, 1999, 159 (01) : 51 - 69
  • [2] Automatic structures
    Blumensath, A
    Grädel, E
    [J]. 15TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 2000, : 51 - 62
  • [3] BLUMENSATH A, 1999, THESIS U AACHEN
  • [4] Carruth PW., 1942, Bull. Amer. Math. Soc, V48, P262, DOI [10.1090/S0002-9904-1942-07649-X, DOI 10.1090/S0002-9904-1942-07649-X]
  • [5] COMMON H, TATA TREE AUTOMATA T
  • [6] Dauchet M., 1990, Proceedings. Fifth Annual IEEE Symposium on Logic in Computer Science (90CH2897-7), P242, DOI 10.1109/LICS.1990.113750
  • [7] DELHOMME C, 2001, RADOS GRAPH NOT AUTO
  • [8] DELHOMME C, 2002, UNPUB AUTOMATIC LINE
  • [9] DELHOMME C, 2001, UNPUB NONAUTOMATICIT
  • [10] FRAISSE R, 1986, STUD LOGIC, V118
12