One-Dimensional Cellular Automata: Injectivity From Unambiguity.
Tom Head · Complex Systems · 1989
New algorithms for deciding the injectivit y of the global update funct ion associat ed with a cellular automaton C A of dimension one are presented. This is done by interpreting each ordered pair dete rmined by the local update function as th e edge of a labeled directed graph GR which has the prope rty that each bi-infinite sequence of states of the cellular automaton is th e 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 pseudofinit e sequences is equivalent to the unambiguity of this automaton. For appropria te 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 finit e set be unambiguous.