One-Dimensional Cellular Automata: Injectivity From Unambiguity
Tom Head
Department of Mathematical Sciences, State University of New York,
Binghamton, New York 13901, USA
Abstract
New algorithms for deciding the injectivity of the global update function associated with a cellular automaton (CA) of dimension one are presented. This is done by interpreting each ordered pair determined by the local update function as the edge of a labeled directed graph GR which has the property that each bi-infinite sequence of states of the cellular automaton is the sequence of input labels of one and only one bi-infinite path in the graph. For an appropriate conversion of GR into a finite automaton, injectivity of the global update function of CA on the set of pseudofinite sequences is equivalent to the unambiguity of this automaton. For appropriate conversions of GR into a finite set of finite automata, the injectivity of the global update function on all sequences is equivalent to the condition that every automaton in the finite set be unambiguous.
