Exploring Reachability Tree for Non-uniform Cellular Automata Under Open Boundary Conditions
Nazma Naskar, B K Sivaraj and Sukanya Mukherjee
Reachability tree proves its power to characterize the elementary cellular automata under logic-0 constant (null) boundary condition and periodic boundary condition. A reachability tree implicitly represents the configuration space of a cellular automaton (CA). It reveals various aspects of CA, such as identification of reachable or non-reachable configuration, cyclic or acyclic configurations, determining reversibility or irreversibility of a given CA, and so on. This paper contributes towards the characterization of cellular automata under the open boundary conditions. A generalized view of reachability tree is reported, which targets the different categories of open boundary condition – adiabatic boundary condition, reflexive boundary condition and constant boundary condition (logic-1 & logic-0). This work establishes that identical CA configuration space can be generated using cellular automata under the above mentioned boundary conditions, for a finite sized CA. This work also reports the characterization of reachability tree for CA under intermediate boundary condition which is another category of open boundary condition cellular automata.
Keywords: Cellular automata, rule mean term (RMT), reachability tree, adiabatic boundary condition, reflexive boundary condition, intermediate boundary condition, constant boundary condition, equivalent cellular automata