Explicit Formulation to the Regular Language Complexity of Some Elementary Cellular Automata Rules

Victor Trafaniuc
Mackenzie University

Pedro de Oliveira
Mackenzie University

A finite automaton is a system defined by states and state transitions that creates a network capable of processing strings of symbols of a certain kind, known as regular languages. In [Wolfram, 1994] it has been shown that the set of possible configurations that can appear in the evolution of one-dimensional cellular automata, at any given time step, can be described by finite automata. In the face of that, one can think of the regular language complexity of a cellular automaton in terms of the number of states and state transition of the finite automaton that characterizes all possible configurations at a given time step.

In [Wolfram, 2002], some functions implemented in Mathematica are presented (NetCAStep, TrimNet, and MinNet) that yield those finite automata, for any given time step, of any one-dimensional cellular automaton rule. After we made an adequate transformation of the output of these functions, from their original list representation to an explicit graph, we went about studying the regular language complexity of the resulting finite automata for all elementary cellular automata rules, that is, the one-dimensional celular automata with nearest neighbours and two states per cell.

By comparing the graphs generated at different time steps, it has been possible to find common structures and clear growth patterns between them for several rules. This was achieved with the help of an algorithm we developed that identifies the rules in which a growth pattern becomes evident when two subsequent time steps are compared and by analyzing them at that point. While the regular language complexity of many rules agreed with the original findings in [Wolfram, 1994], a few have slightly distinct values, a deviation that is in need of an explanation. Above all, out of the analyses carried out, explicit formulae were derived for the regular language complexity of various elementary rules for which no explicit formulation was apparently available so far.

References:
[Wolfram, 1994] S. Wolfram. “Computation theory of cellular automata,” Cellular automata and Complexity:Collected Papers, Addison-Wesley, pp.159-209, 1994.
[Wolfram, 2002] S. Wolfram. A New Kind of Science, Wolfram Media, 2002.

Created by Mathematica  (April 20, 2004)