8.9. Theorem

Let given two sets S1 and S2 EITHER-related states with assembly trees T1 and T2.

If these S1 and S2 have multiple SS with keys k1, … , kM

SS = (S1 × S2)k1, … ,kM

it's states linked to EITHER, that is, there exists some tree build T0.

Evidence

The presence of the multiple SSsuggests that the sets S1 and S2 are divided into channels S1j and S2j (j = 1..M) in each of which:

• the states of one such channel are EITHER-related according to Lemma 8.8, that is, for S1j and S2j exists some assembly tree T1j и T2j.
• there is a multiple sj = s1j × s2j between any two states s1j ∈ S1j and s2j ∈ S2j

For an arbitrary key kj and the corresponding channels S1j and S2j, we define the assembly tree Tj as follows: we connect another tree to each leaf of one of these trees as a subtree.

In this case, such a composite assembly tree defines a set of EITHER-related states, each of which is a multiple of some state s1j ∈ S1j and some s2j ∈ S2j, with each such pair of states participating in such a multiple sj = s1j × s2j for each kj (j = 1..M), and s1j and s2j themselves have kj as their projection by the definition of the multiple.

Now, combine in one search tree T0 all Tj of these arcs, labeled by keys kj.

Such an assembly tree does not change the states formed in each of the Tj because, as just indicated, kj is the projection of each sj ∈ Sj in Tj.

Prev Next