Extensions on the Analysis of Elementary Cellular Automata with Process Graphs
Lia Kassardjian, Pedro Paulo Balbi and Eurico Ruivo
Cellular automata (CAs) are homogeneous dynamical systems discrete in time, space and state variables, with global states being updated by means of a local function acting of the neighbourhood of their constituting parts. The family of elementary CAs (ECAs) is made up by the one-dimensional binary CAs with three next-nearest neighbours. Any one-dimensional CA’s local function can be represented by a De Bruijn graph, in which connected pairs of nodes represent its possible neighbourhoods and the edges connecting them, the corresponding state transitions. De Bruijn graphs are specific kinds of process graphs, which are non-deterministic finite automata that can be used to represent the CA’s regular language obtained at each finite instant of time in the CA’s temporal evolution. The complexity of a process graph is defined defined in terms of the number of its nodes and edges. Previous works already analysed process graphs of ECAs’ temporal evolution and their complexities, as well as their growth patterns over several iterations and limit behaviour. Here, we advance on what is known in this respect for ECAs, expanding previously known complexity data on the evolution of process graphs for various rules, inferring the limit behaviour of two rules and developing a direct way of constructing the process graph associated to a specific rule at any finite number of time steps.
Keywords: Cellular automata, De Bruijn graph, process graph, regular language, limit regular expression
DOI: 10.32908/jca.v18.300824