    1. Algebra 2. Abstract Automata 3. Abstract Network 4. Partition Pairs and Pair Algebra       4.1. Partition Pair       4.2. Mapping       4.3. Examples       4.4. Lemma       4.5. Operators m and M       4.6. Pair Algebra       4.7. Lemma       4.8. Another Definition for Operator M       4.9. S-S, I-S, S-O, I-O pairs       4.10. Applet on Operator M 5. Construction of an Abstract Network 6. Structured Network 7. Additive Decomposition

4. PARTITION PAIRS AND PAIR ALGEBRA

4.1. Partition pair

Def. A partition pair ( , ') on the automaton is an ordered pair of partitions on S such that implies .

4.2. Mapping of the blocks

Def. Given an automaton A, we say that state s goes into state t under input x iff For a subset B of S we define and we say that the subset B goes into set B' under input x iff .

Thus ( , ') is a partition pair (p.p.) on A iff the blocks of are mapped into the blocks of ' by A. That is, for every x in I and in , there exists a in such that .

4.4. Lemma: If ( , ') and ( , ') are partition pairs on A, then

(i) ( ×  '× ') is a p.p. on A and
(ii) ( +  '+ ') is a p.p. on A.

Note that ( ,I) and (0, ) are trivially p.p.

4.5. Operators m and M

Def. If is a partition on S of A, let is a p.p. on A} and is a p.p. on A}.

4.6. Pair algebra

Def. Let L1 and L2 be finite lattices. Then a subset of is a pair algebra on if and only if the two following postulates hold:

1. (x1,y1) and (x2,y2) in implies that (x1×x2, y1×y2) and (x1+x2, y1+y2) are in .
2. For any x in L1 and y in L2, (x,1) and (0,y) are in .
NB! Postulate 1 can be interpreted:
• the combination of information in x1 and x2 is sufficient to compute combined information y1 and y2;
• the combined ignorance in x1 and x2 is sufficient to compute the combined ignorance in y1 and y2.
4.7. Lemma: If is a pair algebra on and (x,y) is in , then x' x and y y' implies that (x',y), (x,y'), and (x',y') are in .

4.8. Another definition for operator m

Def. Let be a pair algebra on . For x in L1 we define in D}. .

NB! Pair algebra associated with an automaton:

4.9. S-S, I-S, S-O, I-O pairs

Def. For a automaton , define:

1. ( , ) is an S-S pair if and only if and t are partitions on S and for all x in I, implies ;
2. ( , ) is an I-S pair if and only if is a partition on I, is a partition on S, and for all s in S, a b( ) implies ;
3. ( , ) is an S-O pair if and only if is a partition on S, is a partition on O, and for all x in I, implies ;
4. ( , ) is an I-O pair if and only if is a partition on I,  is a partition on O, and for all s in S, a b( ) implies . Last update: 3 August, 2004