Computational complexity of dynamical systems: The case of cellular automata

被引：17

作者：

Di Lena, P. ^{[1
]}

Margara, L. ^{[1
]}

机构：

[1] Univ Bologna, Dept Comp Sci, I-40127 Bologna, Italy

来源：

INFORMATION AND COMPUTATION | 2008年 / 206卷 / 9-10期

关键词：

cellular automata; universality; classification;

D O I：

10.1016/j.ic.2008.03.012

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Cellular Automata can be considered discrete dynamical systems and at the same time a model of parallel computation. In this paper we investigate the connections between dynamical and computational properties of Cellular Automata. We propose a classification of Cellular Automata according to the complexities which rise from the basins of attraction of subshift attractors and investigate the intersection classes between our classification and other three topological classifications of Cellular Automata. From the intersection classes we can derive some necessary topological properties for a cellular automaton to be computationally universal according to our model. (C) 2008 Elsevier Inc. All rights reserved.

引用

页码：1104 / 1116

页数：13

共 23 条

[1]

AKIN E, 1993, GRADUATE STUDIES MAT

[2]

[Anonymous], INTRO SYMBOLIC DYNAM

[3] A theory of complexity for continuous time systems [J].

Ben-Hur, A ;

Siegelmann, HT ;

Fishman, S .

JOURNAL OF COMPLEXITY, 2002, 18 (01) :51-86

[4]

Cook M., 2004, COMPLEX SYST, V15, P1, DOI DOI 10.25088/COMPLEXSYSTEMS.15.1.1

[5]

Delvenne JC, 2005, LECT NOTES COMPUT SC, V3354, P104

[6]

Di Lena P, 2006, INT FED INFO PROC, V209, P185

[7]

Durand B., 2003, Discrete Models for Complex Systems, DMCS'03, volume AB of DMTCS Proceedings, P117

[8] Subshift attractors of cellular automata [J].

Formenti, Enrico ;

Kurka, Petr .

NONLINEARITY, 2007, 20 (01) :105-117

[9]

Gilman R., 1988, NOTES CELLULAR AUTOM

[10]

GILMAN RH, 1987, ERGOD THEOR DYN SYST, V7, P105

← 1 2 3 →