[MUSIC] So let's look at this Unicode of this algorithm. We start with the empty hypothesis L. This L is the empty set of implications and it has no counter examples. So in the beginning of our algorithm, our hypothesis admits all algorithm combinations. So the set of models is just the set of all possible algorithm combinations. We submit our current hypothesis to the Oracle. We ask if this is the right hypothesis. And if not we get a counterexample. We process it in a way. We change our hypothesis. And we submit it again to the Oracle and get a new counterexample and so on. Until we find out the true set of implications or the set of implications which is equivalent to the true set of implications. Then the answer given by the oracle will be positive, and will finish the while loop, and will finish the algorithm. So we will have computed the set of implications. Okay, but now let's suppose that we have a counter example X. There may be two cases. Either X is positive or negative. The oracle doesn't tell us. But we can check. All we need is to check is if X is closed under our implication's L. So we compute the closure L of X, we compare it to X. And if L of X equals X, this means that X satisfies our hypothesis but then it must violate the target implication set. Which means it's a negative counterexample. If so, we start looking for an implication that can be strengthened so as to exclude X from the set of models. We check all implications A plus B one by one, we compute the intersection of A and X. We get some set C and first we want this set C to be smaller than A. If it's equal to A then we can't use it as a new premise because it's the same as the old premise. So nothing changes in the implication if we replace A by C. The second condition that C must satisfy, it shouldn't be closed under the target set of implications. So we ask the Oracle if C is a member of the the set of models of L star. If the Oracle says yes, if it says that C is indeed a model of L star, then C doesn't imply anything. So it can't replace A by C, we'll get an implication that is invalid. If however, the oracle says no, then we know that C is not closed, it doesn't satisfy L star, so at least something Is implied by C. And we replace the implication A implies B by the implication C implies B. And that's it for the counterexample X. If we go through all implications, A implies B, and we don't find such an implication, A implies B that can be strengthened. Then we simply add a new implication, X implies M, to the set of our implications, L. Okay, that's what we do with negative counterexamples. If the counterexample, X, is positive, this only means that it violates one or more of the implications from L. So we check all the implications in L in this for loop, and we look at those that are violated by X. If A plus B is violated by X, it means that A is a subset of X but B is not. So we replace B by B intersection X. And now, X satisfies this implication. Well, that's the algorithm. It has been shown in 2011, by Arias and Balcazar, that this algorithm computes not just any set of implications, but the canonical basis of the set of implications guess by the oracle. It can also be shown that this algorithm works in polynomial time. It asks a polynomial number of membership and equivalence queries. And it spends polynomial time to process each of them. So what we get is a polynomial time algorithm for learning implications. [MUSIC]