STATE-OF-ART Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Cellular Automata

Surjectivity and injectivity are the most fundamental problems in cellular automata (CA). We simplify and modify Amoroso's algorithm into optimum and make it compatible with fixed, periodic and reflective boundaries. A new algorithm (injectivity tree algorithm) for injectivity is also proposed. After our theoretic analysis and experiments, our algorithm for injectivity can save much space and 90\% or even more time compared with Amoroso's algorithm for injectivity so that it can support the decision of CA with larger neighborhood sizes. At last, we prove that the reversibility with the periodic boundary and global injectivity of one-dimensional CA is equivalent.