Abstract: | 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) |