Complex Systems

Decision Procedures for Openness and Local Injectivity Download PDF

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.