Low complexity classes of multidimensional cellular automata

被引：4

作者：

Terrier, Veronique ^{[1
]}

机构：

[1] Univ Caen, GREYC, F-14032 Caen, France

来源：

THEORETICAL COMPUTER SCIENCE | 2006年 / 369卷 / 1-3期

关键词：

multidimensional cellular automata; real-time and linear time classes; closure properties; one-way multibead alternating finite automata;

D O I：

10.1016/j.tcs.2006.07.061

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, multidimensional cellular automaton are considered. We investigate the hierarchy designed by the low complexity classes when the dimensionality is increased. Whether this hierarchy is strict, is an open problem. However, we compare different variants and study their closure properties. We present also a correspondence between a main variant of multidimensional real-time cellular automata and one-way multihead alternating finite automata. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：142 / 156

页数：15

共 18 条

[1] ON THE POWER OF ONE-WAY COMMUNICATION [J].