More Decision Algorithms for Global Properties of 1D Cellular Automata
Sébastien Autran and Enrico Formenti
This paper proposes some new decision algorithms for basic properties of one-dimensional cellular automata (CA). In particular, it provides an algorithm for deciding surjectivity on finite configurations. Moreover, by using the classical decision algorithm for surjectivity and injectivity of Sutner, we provide a simple decision algorithm for openness (although its complexity is unchanged). Finally, a complete implication diagram between global properties of one-dimensional CA is provided. When possible the corresponding algorithms for one-sided CA are also given.
Keywords: Decision algorithms, computational complexity, openess, closingness, surjectivity, finite configurations