Compose Algorithm

Question

Hello,

I´ve got another question according the tutors presentation. It´s about the Compose Algorithm this time.

I don´t quite understand the steps made from Screenshot 1 to Screenshot 2. Please explain with the corresponding lines of the algorithm since in my opinion the only two ways to stop the algorithm:

1. x (the variable that gets replaced) is greater than label(phi) (the tree in which x gets replaced) in terms of the variable order
2. x = label(phi)

But I don´t see any of those two cases in Screenshot 1, since the left subtree is always phi and the right subtree is always alpha (or am I wrong?).

Thanks in advance for any responses.

Best regards

Marvin Ballat

Answer 1

There are again multiple steps happening at once. If we simply follow the algorithm, then the b node is "pulled up" and the Compose-Node goes down one level. Once phi is only True or False case 1 (from your question) applies.

Here we can see this directly, because a does not occur in phi. Therefore case 2 will never apply. We will simply go down recursively until finally case 1 applies. Intuitively: We want to replace a. a does not occur in phi. Therefore we leave phi as it is.

This is a shortcut that is easy to see for humans, and you are allowed to do that in the exam (but better write a comment next to it). The computer can't see that since it only goes through the tree node by node and does not have an "overview".

Comments

Alright, that makes a lot of sense. Thank you!