pre-injectivity
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 .
Lemma 1
For a cellular automaton
the following are equivalent.
-
1.
has no mutually erasable patterns.
-
2.
is pre-injective.
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
(1) |
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.
References
- 1 Ceccherini-Silberstein, T. and Coornaert, M. (2010) Cellular Automata and Groups. Springer Verlag.
- 2
Title | pre-injectivity |
---|---|
Canonical name | Preinjectivity |
Date of creation | 2013-03-22 19:22:04 |
Last modified on | 2013-03-22 19:22:04 |
Owner | Ziosilvio (18733) |
Last modified by | Ziosilvio (18733) |
Numerical id | 4 |
Author | Ziosilvio (18733) |
Entry type | Definition |
Classification | msc 37B15 |
Classification | msc 68Q80 |
Defines | mutually erasable patterns (cellular automaton) |