ONE-WAY CELLULAR-AUTOMATA ON CAYLEY-GRAPHS

被引：18
作者：
ROKA, Z
机构：
[1] Laboratoire de l'Informatique du Parallélisme, Ecole Normale Supérieure de Lyon, F-69364 Lyon Cedex 07
来源：
THEORETICAL COMPUTER SCIENCE | 1994年 / 132卷 / 1-2期
关键词：
D O I：
10.1016/0304-3975(94)90236-4
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The notion of one-dimensional one-way cellular automata has been introduced to model cellular automata with only a one-way communication between two neighbor cells. In this paper, we generalize this notion to cellular automata working on different communication graphs We present some sufficient conditions for a cellular automaton to be stimulated by a one-way cellular automaton having the same underlying graph, and we give some bounds on the simulation-time of this mimic.
引用
收藏
页码：259 / 290
页数：32
相关论文
共 11 条
  • [1] Bollobas B., 1979, GRAPH THEORY INTRO C
  • [2] BURNSIDE W, 1987, THEORY GROUPS FINITE
  • [3] CAYLEY A, 1878, P LOND MATH SOC, V1, P126
  • [4] Cayley A., 1878, AM J MATH, V1, P174
  • [5] CHOFFRUT C, 1984, ACTA INFORM, V21, P393, DOI 10.1007/BF00264617
  • [6] DUKE RA, 1979, CAN J MATH, V18, P817
  • [7] ONE-WAY BOUNDED CELLULAR AUTOMATA
    DYER, CR
    [J]. INFORMATION AND CONTROL, 1980, 44 (03): : 261 - 281
  • [8] MOSER WOJ, 1965, GENERATORS RELATIONS
  • [9] Smith AR., 1972, JCSS, V6, P233, DOI DOI 10.1016/S0022-0000(72)80004-7
  • [10] WHITE AT, 1973, NORTH HOLLAND MATH S
12