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
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
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:
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:
Last update: 3 August, 2004