Fundamenta Informaticae - Volume 52, issue 1-3

Authors: Sanders, Peter | Vollmar, Roland | Worsch, Thomas

Article Type: Research Article

Abstract: Using cellular automata as models of parallel machines we investigate constraints for the energy consumption of r-dimensional machines which are motivated by physical limitations for the case r=3. Depending on the operations which must be considered to dissipate energy, some relations between the relative performance of 2-dimensional and 3-dimensional machines are derived. In the light of these results it seems imperative that for feasible models of computation energy consumption has to be considered as …an additional complexity measure. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 233-248, 2002

Authors: Sutner, K.

Article Type: Research Article

Abstract: We exhibit one-dimensional cellular automata whose reachability and confluence problems have arbitrary r.e. degree of unsolvability.

Keywords: cellular automata, intermediate degrees, confluence problem

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 249-256, 2002

Authors: Umeo, Hiroshi | Kamikawa, Naoki

Article Type: Research Article

Abstract: We introduce a special new class of cellular automata(CA) whose inter-cell communication is restricted to 1-bit. Several design examples for 1-bit inter-cell communication cellular algorithms are given. It is shown that infinite non-regular sequences such as {2^n | n = 1, 2, 3,..}, {n^2 |n = 1, 2, 3,..} and Fibonacci sequences can be generated in real-time by cellular automata with 1-bit inter-cell communications. In addition, twice real-time prime generation algorithm is also given.

Keywords: cellular automaton, 1-bit inter-cell communication, real-time non-regular sequence generation algorithm, linear-time prime generation algorithm, sieve of Eratosthenes

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 257-275, 2002

Authors: Weimar, Jörg R.

Article Type: Research Article

Abstract: Cellular automata for reaction-diffusion systems are efficient enough to make the simulation of large three-dimensional systems feasible. The principal construction mechanisms used here are not much different from those for two-dimensional cellular automata. Diffusion is realized through a local averaging, and all the nonlinear reaction terms are collected in a table-lookup. The special issue in three dimensions is the need to increase time- and space- scales as much as possible to achieve sufficient system sizes. …This can be done through the use of numerical integration schemes for constructing the lookup table, and through the use of special diffusion operators. We present examples of complex three-dimensional behaviors in an excitable reaction-diffusion system and in a model of a pattern-forming chemical reaction. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 277-284, 2002