## 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.