Narrow Results

In this paper, we propose new difference equations which can generate the evolution rules of cellular automata.

The concept of complexity index is of key importance in the systematic analysis of the dynamics of Cellular Automata (CA); nevertheless, it has been defined only for the special case of 1D elementary CA. In this paper, we first introduce a complexity index for outer-totalistic binary CA with arbitrary dimension and neighborhood by means of a rigorous mathematical theory, and then propose a method to find it easily, given only the truth table of an outer-totalistic binary CA rule. Through our technique, we study in detail both 1D and 2D elementary CA rules, including the well-known Game of Life.

This chapter proposes a design of cell circuits for implementing cellular-automaton devices that perform morphological picture processing. To produce the morphological processing, we present the idea of using the silicon functional device, νMOS FET. We designed sample cell circuits for several morphological processing (noise cleaning, edge detection, thinning and shrinking in an image). A low dissipation of about 10 µW per νMOS FET threshold logic circuits can be expected at 1 MHz operation; therefore, 10⁵ or more cells that operate in parallel can be integrated into an LSI.