Let be a Cartesian product. Call two elements almost equal if the set is finite. A function is said to be pre-injective if it sends distinct almost equal elements into distinct elements, i.e., if implies .
If is finite, pre-injectivity is the same as injectivity; in general, the latter implies the former, but not the other way around. Moreover, it is not true in general that a composition of pre-injective functions is itself pre-injective.
A cellular automaton is said to be pre-injective if its global function is. As cellular automata send almost equal configurations into almost equal configurations, the composition of two pre-injective cellular automata is pre-injective.
Pre-injectivity of cellular automata can be characterized via mutually erasable patterns. Given a finite subset of , two patterns are mutually erasable (briefly, m.e.) for a cellular automaton on if for any two configurations such that and one has .
For a cellular automaton the following are equivalent.
has no mutually erasable patterns.
Proof. It is immediate that the negation of point 1 implies the negation of point 2. So let be two distinct almost equal configurations such that it is not restrictive to suppose that is symmetric (i.e., if then ) and , the identity element of , belongs to . Let be a finite subset of such that and let
we shall prove that and are mutually erasable. (They surely are distinct, since .)
So let satisfy and Let . If , then , because by construction if then as well, because by construction Since and are arbitrary, and are mutually erasable.
- 1 Ceccherini-Silberstein, T. and Coornaert, M. (2010) Cellular Automata and Groups. Springer Verlag.
|Date of creation||2013-03-22 19:22:04|
|Last modified on||2013-03-22 19:22:04|
|Last modified by||Ziosilvio (18733)|
|Defines||mutually erasable patterns (cellular automaton)|