Table 10: Regular Language Complexities

Regular language complexities.

The set of configurations that can appear after steps in the evolution of a one-dimensional cellular automaton can be shown to form a regular formal language (see pages 159--202 in this book). Possible configurations thus correspond to possible paths through a finite graph which represents the grammar for the regular language. The table gives the minimum number of nodes in the graphs for such grammars; the number of arcs is given in brackets in each case. The notation. indicates that the regular language is the same as at the preceding time step.

Entries in the last column of the table give sizes of graphs for regular languages representing limiting sets of states that can be reached after any number of steps.

The size of a regular grammar gives a measure of the ``complexity'' of the set of configurations it describes. Notice that the grammar specifies merely which configurations can possibly occur; it does not account for the probabilities of different configurations.

The graphs used for the table represent possible sequences of site values that occur in configurations read from left to right. Rules related by reflection may in general yield different regular languages. The table thus includes minimal representatives for all rules from table 1 not related by complementation.

Entries in the table for that have been left blank were not found. They are probably . The growth of regular language complexities is bounded by .

For some rules, it has been possible to find explicit forms for the regular languages produced after any number of time steps. Formulae for complexities in these cases are listed in the table. In many cases, it is however suspected that the limiting set does not form a regular language, and may in fact be non-recursive.

Table by Lyman P. Hurd (Mathematics Department, Princeton University). (Original program by S. Wolfram.)

previous  l  next