Decision Procedures for Openness and Local Injectivity
Stephen J. Willson
Department of Mathematics, Iowa State University,
Ames, Iowa 50011, USA
Abstract
Let F be a cellular automaton on the space of all sequences from a finite alphabet. From the local description of F a finite labeled digraph is constructed with a distinguished subdigraph. The surjectivity and openness of F are proved to correspond to properties of these digraphs. Similarly, another finite labeled digraph is constructed with a distinguished subset of its vertex set. The injectivity and local injectivity of F are proved to correspond to properties of this digraph and its subset. All the relevant properties can be checked in finitely many steps. Analogous results are also obtained for biinfinite sequences.
