Hello,
this is intended to be an explanation for those of you who might have had similar problems as I had when checking the duality laws for predecessors/successors. The explanation is actually contained in the third video on transition systems. But I had some struggle with it nonetheless, because I needed to see it explicitly. Please correct me if my explanations are wrong or if you find a mistake.
For the existential predecessor set of some set Q2 the duality law reads as the following:
pre∃(Q2) = S1 \ pre∀(S2 \ Q2)
In order to understand what the sets S1 and S2 are, think of the transition relation as R⊆S1×S2. The set Q2, for which we want to know pre∃(Q2), is contained in S2, i.e. Q2⊆S2. Similarly, pre∃(Q2)⊆S1.
Now, take the duality law and complement both sides:
S1 \ pre∃(Q2) = S1 \ (S1 \ pre∀(S2 \ Q2))
Since the right side is now complemented two times, i.e. we get the original set, it can be simplified to pre∀(S2 \ Q2), whereby the duality now reads as:
S1 \ pre∃(Q2) = pre∀(S2 \ Q2)
Now, it is much more understandable than before. To understand it, start with the right side:
pre∃(Q2) is the set of all states in S1 that have at least one transition to some state in Q2. Hence, when complementing it, i.e. S1 \ pre∃(Q2), we get the set of states that have no transition into Q2. This means, that those states have all their transitions (if any at all) going into the state set S2 \ Q2. This can also be expressed as pre∀(S2 \ Q2), which is actually the right side of the complemented duality law.
For checking the other duality laws we can proceed in exactly the same way: first complement the law, then understand the right side and check whether the left side has the same meaning.
Best regards,
choehne
