In this introduction we review the basics of cellular automata and give a short survey of some areas of research concerning cellular automata. This is done to tit the papers of the present special issue into a general frame. 0 1997 Elsevier Science B.V. Keywords: Cellular automata 1. Basics of cellular automata Cellular automata (CA) have been introduced by John von Neumann following a suggestion of Stanislaw Ulam. Von Neumann was looking for a theoretical framework which would allow the construction of a self-replicating device capable to do something 'meaningful'. The CA model allowed von Neumann to devise a structure which is computation universal as well as construction universal; i.e., it can be programmed to compute any computable function and/or to construct any other 'machine'. Von Neumann never published a paper on CA himself, but after his death his notes were edited, completed and made available by Arthur Burks [&I.
The fundamental idea was to consider a two-dimensional arrangement of deterministic identical finite-state machines, called cells, which work synchronously according to the same transition rule, depending only on the local information provided by the states of a constant number of neighboring cells. In order to have a common basis of notations we now turn to a formal description of CA.