Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers

1.6k comments

543 users

+3 votes
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
in * TF "Emb. Sys. and Rob." by (770 points)
edited by
This is a great explanation of the relationships among the existential/universal predecessors. It is good to play around like this with the definitions to really understand why they are made as they are.

Excellent!
Thank you very much!
Thank you for this helpful addition. Here's how I read the duality so far:

 pre∃(Q2) = S1 \ pre∀(S2 \ Q2)

The states with at least one transition to Q2 (that's pre∃(Q2)) are precisely those states of S1 whose transitions don't all (that's S1 \ pre∀(…) ) end somewhere else than in Q2 (that's S2 \ Q2).
Thank you very much! It took me some time to get used to it, but it's a nice way how to read the meaning directly from the expression.

1 Answer

0 votes

This is a great explanation of the relationships among the existential/universal predecessors. It is good to play around like this with the definitions to really understand why they are made as they are. Excellent!

by (166k points)
Imprint | Privacy Policy
...