×

More decision algorithms for global properties of 1D cellular automata. (English) Zbl 1467.68102

Summary: 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.

MSC:

68Q80 Cellular automata (computational aspects)
37B15 Dynamical aspects of cellular automata
PDFBibTeX XMLCite
Full Text: Link