[MUSIC] As I already indicated, there are many equivalencies between label transition systems. In this lecture we will address a few of them that you have not yet seen. Label transition systems are traditionally used not in the study of behavior of processes, but in the study of languages and compilers, parsing, scanning. So, one of things people do there is that they want to read a text efficiently. So suppose we have a text. And we want to recognize, for instance, the word book, and we put here the termination symbol to indicate that the word ends there. And that's a way to recognize an OP like book in a text. Or we could want to recognize different words, say ball. And let's add a third word, namely boots. And these are words that we would like to officially recognize in a text. So, what we see here is that we have words and that are typically traces ending in a termination symbol. Two transition systems are equal if they recognize exactly the same words, namely, beside the two transition systems are language equivalent if they have exactly the same set of words. Now, there's a problem with this transition system, namely, if you read a word, and you expect the word book, then you take a branch of this transition system. But if the second letter then turns out to be an A, we have to backtrack and take the second branch, and that is inefficient. So what would be efficient is to make a deterministic transition system that is exactly language equivalent to this original. And that can be done in this way. So we want to recognize the ball, the book, and the boot. And now when we see the B in the text and we cannot make a distinction, if we recognize an A or an O in the text, we can immediately decide to take the upper branch or to stay with the lower branches. In this way we can recognize a ball, or we recognize a boot. And then the question is whether a K will appear or a T will appear. If K appears, we recognize book and otherwise, boot. And this is an efficient way. So the question to make scanning efficient is that you simply have to constrict a language equivalent deterministic labelled transition system. Which is equivalent to the set transition system recognizing the set of words. A completely different equivalence is completed trace equivalence, and that comes from the observation that some people think that they can recognize a deadlock. So suppose that we had a behavior. And after sometime, there's an a, and then after a while, there's a b. And after even more time, there's a c. Then it can be that we simply do not observe anything anymore, and we can say that the system is in this deadlock. So what we can say is that the completed trace of the system is typically every trace that ends in a deadlock or that ends in a terminating state. So for this particular example, we have a, b, and c as the completed trace belong to this example. And if you have this example, then the complete traced is r, a and a followed by the termination symbol. So, are these transition systems completed trace equivalent? Well the answer is very simple, namely the completed traces are ab and ac. And so we can conclude that they are completed trace equivalent. But there is a problem with completed trace equivalents, and that is that it is not preserved in the common operations. So an operation that we can apply is an operation where we block a particular action. We simply say that an action cannot happen anymore, so in this case we could block the action c. And blocking an action is different from hiding an action. Hiding means that you make the option unobservable, but it can still happen. Blocking means that you simply prevent it from happening. So if you block c in the left diagram, we simply remove the transition. And if we block c in the right diagram, we also remove this transition. And now something nasty is happening. What we can see is the completed traces of the diagram at the right after removing the c are a and ab. And at the left, it's only ab, so we had two completed trace equivalent behaviors. We apply an operations to these equivalent objects, and all of a sudden they become different. And that is extremely undesired. So, they are not completed trace equivalent anymore after removing the sheet. And this is so annoying that people invented a new equivalence namely failure equivalence, or failures equivalence. And that is the complete trace congruence under standard operators that are applied on behavior. And that means that that is the equivalence that relates all the processes in such a way that you can never distinguish between processes by applying operations on them. But the definition of failure equivalence is rather involved. It starts with the so-called notion of a refusal set. So a refusal set is a set of actions that cannot be done in a particular stage. So in initial state of the diagram, we cannot do the b, the c, and we can also not terminate. But there's another refusal set because we can also not do a b and a c. And actually any subset of this largest refusal set is also a refusal set. Even the empty set is a refusal set. In the second state, we can see that we cannot do an a and a termination. And that means that a and terminations are all refusal sets. And in this state at lower left part, we see that {a, b, c, tick} are actions that cannot be done. And here we can see that {a, b, c} are actions that cannot be done. So this set and all their subsets, these two sets and their subsets are refusal sets, okay. Given that we know what refusal sets are, we define a notion of a failure pair. And a failure pair is the following. It is a trace and a refusal set. So in this state at the top, it's the empty trace that's the trace towards the initial state and a refusal set. And that is every set which was a subset of b, c, and tick. And the second state has the refusal bear a and U being the subset of a and tick. And this state at the end has the trace ab and refusal sets being subsets of a, b, c and tick. And this state at the bottom right has the trace ac and ac tick and that are the failure pairs. When are two transition systems failures equivalent? Well they are failures equivalent if they have the same failure pairs. So are these two sufficient systems failures equivalent? And generally that's unpleasant because there are so many failure pairs, but in some cases, you can see the difference. So in this particular case, what we can see is that after doing the a action in the right diagram, we cannot do a b. And we do not have the same failure pair at the left because after doing an a at the left, we always have the option to do a b. So we can see that these are not failures equivalent because we find a failure pair, namely (a, {b}) available in the LTS at the right, but not any label transition system at the left. Okay, let's do an exercise. Are these two transition systems language equivalent? These two slightly more complex transition systems have all kinds of interesting properties. Now the question is, are they completed trace equivalent? And if we considered the same transition systems again, are they failures equivalent? Okay, we defined what language equivalence was. We defined completed trace equivalence, and indicated what failures equivalence was. And these are only a few of the whole plethora of equivalences, but I think we looked at those that are the most important. Thank you for watching. In the next video, I will shortly address when you have to use which equivalence. [MUSIC]