Partition Pairs and Pair Algebra Theory

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

Example of partition pairs

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 L₁ and L₂be finite lattices. Then a subset of is a pair algebra on if and only if the two following postulates hold:

(x₁,y₁) and (x_2,y₂) in implies that (x₁×x₂, y₁×y₂) and (x₁+x₂, y₁+y₂) are in .
For any x in L₁ and y in L₂, (x,1) and (0,y) are in .

NB! Postulate 1 can be interpreted:

the combination of information in x₁ and x₂ is sufficient to compute combined information y₁ and y₂;
the combined ignorance in x₁and x₂ is sufficient to compute the combined ignorance in y₁ and y₂.

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 L₁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:

(,) is an S-S pair if and only if and t are partitions on S and for all x in I, implies ;
(,) 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, ab() implies ;
(,) 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 ;
(,) 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, ab() implies .

Last update: 3 August, 2004