TY - CHAP

T1 - Characterizing configuration spaces of simple threshold cellular automata

AU - Tosic, Predrag T.

AU - Agha, Gui A.

PY - 2004

Y1 - 2004

N2 - We study herewith the simple threshold cellular automata (CA), as perhaps the simplest broad class of CA with non-additive (that is, non-linear and non-affine) local update rules. We characterize all possible computations of the most interesting rule for such CA, namely, the Majority (MAJ) rule, both in the classical, parallel CA case, and in case of the corresponding sequential CA where the nodes update sequentially, one at a time. We compare and contrast the configuration spaces of arbitrary simple threshold automata in those two cases, and point out that some parallel threshold CA cannot be simulated by any of their sequential equivalents. We show that the temporal cycles exist only in case of (some) parallel simple threshold CA, but can never take place in sequential threshold CA. We also show that most threshold CA have very few fixed point configurations and few (if any) cycle configurations, and that, while the MAJ sequential and parallel CA may have many fixed points, nonetheless "almost all" configurations, in both parallel and sequential cases, are transient states. Finally, motivated by the contrasts between parallel and sequential simple threshold CA, we try to motivate the study of genuinely asynchronous CA.

AB - We study herewith the simple threshold cellular automata (CA), as perhaps the simplest broad class of CA with non-additive (that is, non-linear and non-affine) local update rules. We characterize all possible computations of the most interesting rule for such CA, namely, the Majority (MAJ) rule, both in the classical, parallel CA case, and in case of the corresponding sequential CA where the nodes update sequentially, one at a time. We compare and contrast the configuration spaces of arbitrary simple threshold automata in those two cases, and point out that some parallel threshold CA cannot be simulated by any of their sequential equivalents. We show that the temporal cycles exist only in case of (some) parallel simple threshold CA, but can never take place in sequential threshold CA. We also show that most threshold CA have very few fixed point configurations and few (if any) cycle configurations, and that, while the MAJ sequential and parallel CA may have many fixed points, nonetheless "almost all" configurations, in both parallel and sequential cases, are transient states. Finally, motivated by the contrasts between parallel and sequential simple threshold CA, we try to motivate the study of genuinely asynchronous CA.

UR - http://www.scopus.com/inward/record.url?scp=27944481898&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=27944481898&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-30479-1_89

DO - 10.1007/978-3-540-30479-1_89

M3 - Chapter

AN - SCOPUS:27944481898

SN - 3540235965

SN - 9783540235965

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 861

EP - 870

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Sloot, Peter M. A.

A2 - Hoekstra, Alfons G.

A2 - Chopard, Bastien

PB - Springer

ER -