Applications of Propositional Logic to Cellular Automata


Click here to access the text


In this paper we give a new proof of Richardson’s theorem : a global function G_{A} of a cellular automaton A is injective if and only if the inverse of G_{A} is a global function of a cellular automaton. More- over, we show a way how to construct the inverse cellular automaton using the method of feasible interpolation. We also solve two problems regarding complexity of cellular automata formulated by Bruno Durand.