The Structure of Hierarchical Motion Representation of 2-state Number Conserving Cellular Automata
G.T. Kong, K. Imai and T. Nakanishi
A one-dimensional two-state number conserving cellular automaton (NCCA) is a cellular automaton whose states are 0 or 1 and where cells take states 0 and 1 and updated their states by the rule which keeps overall sum of states constant. It can be regarded as a kind of particle-based modeling of physical systems and has another intuitive representation, motion representation, based on the movement of each particle. We introduced a kind of hierarchical interpretation of motion representations to understand the necessary pattern size to each motion. We show all NCCAs with neighborhood size n can be derived from that of n − 1 and give an algorithm to compute the hierarchical motion representation of an NCCA employing the result.
Keywords: Cellular automata, motion representation, number conservation