is recognizable

by giving an algorithm that accepts only two different IFSs

Definitions

Let denote Φ the finite set of matrices of an IFS.
    
In general, the matrices are of the affine form
where with and .
is the dimension of and is the translation component of a affine matrix .

Let    
and    .

Let be the set of the identity matrix of dimension .
Then we can define the set of all products of the IFS at iteration level
     recursively.
In words, we compute the set of matrices of level from the set of matrices of level by multiplying each matrix with each from the right.
Equivalently, .
Elements from correspond to matrices where . can be called a limit point.

Now we impose a last condition for an IFS, the manifold condition: We require an IFS to satisfy and w.l.o.g. such that for any ( for any ).
Note, that otherwise the IFS reduces to , i.e. the limit set consists only of one element.

Let and denote the finite set of matrices of the two IFS, and .

• Definition : The IFSs and are not equivalent, iff there is an open interval ( Borel-measure ) such that an infinite number of limit points
    either built from elements of are in whereas no limit points from are in ,
    or built from elements of are in whereas no limit points from are in .
Note, otherwise .

Comparision of two IFS with dimension d=1

Let Φ and Ψ denote the finite set of matrices of the two IFS, and . In general a matrix is of the form
where and .

Example: An IFS in 1D that converges to the cantor-set is given by with
and .

Acording to the definitions above, and is the set of all products at level k of iteration. Note, to compute level , we multiply each with each from the right. The collection of all products form .

Let , and with . Then
    .

To understand the analysis for comparing two IFS of dimension 1, it is neccessary to understand the 2x2-matrix-multiplication for this special matrix format. In other words, we investigate the outcome more:

• , which means in the interpretation of the points in the plane, we are getting closer to the y-axis.

• the change of the translative component from level k to level is
    
hence, "only" of magnitude .

In the following, we yield an upper bound for β and take advantage of making   sufficiently small.

To yield an upper bound for the translative component β of all matrices of an IFS at the level , we get inspiration from
    

and understand that in general, we yield the expression
     for .

Since Φ contains a finite number of matrices
     and
     are well defined.
Note that still . With these values we can bound    such that

    

The sum is the geometric series and we can conclude, letting -> ∞
    .

Hence, no product can be formed with translation part β with magnitude greater than .
In our example for the cantor set, we yield that . This corresponds to the steepest possible slope in the figure.

We apply the previous result to consider obtainable limit points from an element at level k. It follows that . is refered to as the event horizon of in .

Side note: In graphical terms one could say, that the event horizon forms a "cone" with top , which is unioned with the mirror cone at . I.e. we cannot yield matrices in greater levels which would correspond to points outside the previously described area.

• Algorithm 1: The previous considerations immediately give us an algorithm at hand, of which we prove below, that it accepts for two IFSs and :
We compute the elements of and simultaneously for increasing levels . At each level , we consider for all the set , of which there are finitely many, with the union of all , defined for Ψ analogously, and conversly. We can stop if
    either    a)     for some
    or    b)     for some .
Because a) and the manifold condition ⟹ ∃ that generates infinitely many limit points, that lie separated from all limit points of Ψ. Similarly b).

• Lemma 1: Let and Ψ be two IFSs. Algorithm 1 accepts input iff .
Proof: are accepted w.l.o.g. a) is satisfied, i.e. such that is disjoint from . Yet is closed in . If we continue recurring from to some level , we yield a with with due to the manifold condition. Hence, we can construct an open set in containing entirely and infinite number of limit points of and none of .
with open such that w.l.o.g. infinitely many input points of lie in , but no limit points of are in . such that with . This will satisfy a). •

Multidimensional IFS

In order to extend this result to higher dimensional IFS, i.e. , treat as a matrix and as the translation vector in the previous computations. One can choose the 2-norm for matrices and vectors.

Remark: