Fundamenta Informaticae

A necessary and sufficient condition for a one-dimensional q-state n-input cellular automaton rule to be number-conserving is established. Two different forms of simpler and more visual representations of these rules are given, and their flow diagrams are determined. Various examples are presented and applications to car traffic are indicated. Two nontrivial three-state three-input self-conjugate rules have been found. They can be used to model the dynamics of random walkers.

One-way and two-way cellular language acceptors with restricted nondeterminism are investigated. The number of nondeterministic state transitions is regarded as limited resource which depends on the length of the input. We center our attention to real-time, linear-time and unrestricted-time computations. A speed-up result that allows any linear-time computation to be sped-up to real-time is proved. The relationships to deterministic arrays are considered. For an important subclass a characterization in terms of deterministic language families and $\epsilon$-free homomorphisms is given. Finally we prove strong closure properties of languages acceptable with a constant number of nondeterministic transitions.

Subshift behaviors of one-dimensional (1D) bi-infinite Cellular Automata are studied. In particular the conditions under which subshifts generated by CA 1D dynamical systems exhibit some components of the chaotic behavior (in particular transitivity, topological mixing and strong transitivity) are investigated. A complete classification of all elementary (Boolean radius one) CA with respect to subshifts is given.

In this paper, we consider the pebble automata introduced by Blum and Hewitt, but now moving through the unbounded plane Z^2. We are interested in their ability to recognize families of dotted figures. Contrary to the bounded case studied by Blum and Hewitt, the hierarchy collapses: there are families recognized with 0, 1, 2 and 3 pebbles, but each family recognized with more than three pebbles is recognized with exactly 3 ones. This result is connected to the existence of an intrinsically universal} 3-pebble-automaton. We formally define the underlying universality notion, and prove that there exists some 3-pebble automaton intrinsically universal, but no such automaton with only 2 pebbles.

We study the Firing Squad Synchronization Problem (FSSP) on a cellular automaton (CA) having number-conservation property. In a number-conserving CA, all states of cells are represented by (tuples of) non-negative integers and the total number of its configuration is conserved throughout its computing processes. But, if we use a usual framework of CA in which each state of a cell is represented by a single integer, it is not possible to make every cell to be in the same firing state, which should be different from the soldier state, under the usual FSSP condition without violating the number-conservativeness. So, we employ the framework of a partitioned cellular automaton, and define a number-conserving partitioned cellular automaton (NC-PCA). Its cell is divided into three parts, and hence each cell is represented by a triple of non-negative integers. In NC-PCA, only the constraint that the local transition function should satisfy a number-conserving condition is supposed. Thus, it makes relatively easy to construct an NC-PCA. Because each cell can hold three non-negative integers, it is possible to represent different states even if the sum of three numbers are equal. Using this technique, we show that Minsky's 3n time solution can be embedded into an NC-PCA, having an integer at most 9 in each part of a cell.

We show relations between several concepts of stability based on topological and measure-theoretical concepts in the Cantor and Besicovitch topological spaces. These concepts elucidate the behavior of cellular automata in which successively larger and larger regions are homogenized.

Historically, cellular automata were defined on the lattices Z^n, but the definition can be extended to bounded degree graphs. Given a notion of simulation between cellular automata defined on different structures (namely graphs of automata), we can deduce an order on graphs. In this paper, we link this order to graph properties and explicit the order for most of the common graphs.

We present two generalizations of cellular automata where transitions from one configuration to the next are no longer deterministic but depend on some element of randomization. The main topic is a model which not only takes into account the probabilities of cells being in certain states but also their dependencies. It formalizes the approach of ``randomized simulations'' often used for the modeling of real phenomena. In this paper the power of stochastic CA as language recognizers is investigated. Generalizations of well-known tools (stochastic signals and product automata) are used to prove that stochastic CA are strictly more powerful than deterministic CA and stochastic finite automata (which are known to recognize uncountably many languages).

We state a definition of the simulation of graph automata, which are machines built by putting copies of the same finite-state automaton at the vertices of a regular graph, reading the states of the neighbors. We first present the notion of simulation and link it to intrinsic graph properties. Afterwards, we present some results of simulation between such graph automata, comparing them to the cellular automata on Cayley graphs. The graphs considered here are planar, with the elementary cycles of the same length, and form regular tilings of the hyperbolic plane. We conclude with a possible speed hierarchy.

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.

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

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.

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.