Analysis of Reachability Tree for Identification of Cyclic and Acyclic CA States

摘要

This paper reports a scheme to identify cyclic/acyclic states from the state space of cellular automata (CA). We analyze the reachability tree to do this. An algorithm is presented to count the cyclic states. We introduce a concept of tree merging for identifying cyclic and acyclic states. To our knowledge, this is the first work to efficiently identify cyclic/acyclic states from the state space of nonlinear CA. Since cyclic states can only form attractors, the identification of cyclic states would help us to characterize CA attractors.