Some applications of propositional logic to cellular automata

In this paper we give a new proof of Richardson's theorem 31]: a global function G_?? of a cellular automaton ?? is injective if and only if the inverse of G_?? is a global function of a cellular automaton. Moreover, we show a way how to construct the inverse cellular automaton using the method of feasible interpolation from 20]. We also solve two problems regarding complexity of cellular automata formulated by Durand 12] (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)