Let X=iIXi be a Cartesian product. Call two elements x,yX almost equal if the set Δ(x,y)={iIxiyi} is finite. A function f:XX is said to be pre-injective if it sends distinct almost equal elements into distinct elements, i.e., if 0<|Δ(x,y)|< implies f(x)f(y).

If X 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 compositionMathworldPlanetmath of pre-injective functions is itself pre-injective.

A cellular automatonMathworldPlanetmath is said to be pre-injective if its global function is. As cellular automata send almost equal configurationsMathworldPlanetmathPlanetmath 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 E of G, two patterns p1,p2:EQ are mutually erasable (briefly, m.e.) for a cellular automaton 𝒜=Q,𝒩,f on G if for any two configurations c1,c2:GQ such that ci|E=pi and c1|GE=c2|GE one has F𝒜(c1)=F𝒜(c2).

Lemma 1

For a cellular automaton A=Q,N,f, the following are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath.

  1. 1.

    𝒜 has no mutually erasable patterns.

  2. 2.

    𝒜 is pre-injective.

Proof. It is immediate that the negationMathworldPlanetmath of point 1 implies the negation of point 2. So let c1,c2:GQ be two distinct almost equal configurations such that F𝒜(c1)=F𝒜(c2): it is not restrictive to suppose that 𝒩 is symmetricPlanetmathPlanetmath (i.e., if x𝒩 then x-1𝒩) and e, the identity elementMathworldPlanetmath of G, belongs to 𝒩. Let Δ be a finite subset of G such that c1|GΔ=c2|GΔ, and let

E=Δ𝒩2={gGzΔ,u,v𝒩g=zuv}: (1)

we shall prove that p1=c1|E and p2=c2|E are mutually erasable. (They surely are distinct, since ΔE.)

So let γ1,γ2:GQ satisfy γi|E=pi and γ2|GE=pi=γ2|GE. Let zG. If zΔ𝒩, then F𝒜(γ1)(z)=F𝒜(γ2)(z), because by construction γi|z𝒩=ci|z𝒩; if zGΔ𝒩, then F𝒜(γ1)(z)=F𝒜(γ2)(z) as well, because by construction γ1|z𝒩=γ2|z𝒩. Since γ1 and γ2 are arbitrary, p1 and p2 are mutually erasable.


  • 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)