[MUSIC] So, in the general case, we don't know the length, and we will not specify it here. But we will allow variables. So, the oracle, please guess a pattern. Okay, the pattern is guessed. Now, what questions should we ask? From the previous video, we see that membership, equivalence, and subset queries don't really get us too far. So let's use superset queries. Well, in the previous example, it somehow helped to know the length of the pattern. Let's see if we can learn the length of the pattern, or if we can compute the length of the pattern, using a small number of superset queries. First, what happens if I submit the following hypothesis as a superset query? So, just one variable x. What will be the answer? So, the answer is "yes". And this is because x can be replaced by any binary string. So x is the most general pattern. It covers all binary strings. The language defined by x is a superset of any other language. Okay, but now what happens if we use xy? Well, now this pattern also matches almost all the strings except for those that contain exactly one symbol. And this is because x and y are variables that can be replaced only by non-empty binary strings. So, x must be replaced by at least one symbol and y must be replaced by at least one symbol. So xy has to have at least two symbols. Any string in the language of xy must have at least two symbols. So the oracle says "yes". And this means that the language defined by the pattern guessed by the oracle doesn't include any one-symbol words, because now this word is matched by this pattern xy, and still xy is a superset of the target pattern. And, so that's how we can compute the length of the target pattern. Let's add the third variable, xyz. Still yes. xyzu, still yes. v, yes, w, yes, s, yes, t, yes. Well, okay. p, no. And we've got a counterexample and this counterexample contains one, two, three, four, five, six, seven, eight symbols. And our pattern has one, two, three, four, five, six, seven, eight, nine symbols. So every word that matches our hypothesis must have at least nine symbols and the target language contains a word that has only eight symbols. That's why we know that the length of the target pattern is eight. All right, so that's the first thing. We've found out the length of the pattern, we have computed it. How many queries have we asked? Well, so the length of the pattern is eight and we asked exactly eight queries. Now let's see, so we have eight positions in our pattern, in the target pattern. And now we have to decide which of these positions are occupied by constants and which are by variables. And that's easy to do. So let's see if we can have a zero at the first position. We just replace x by 0, and submit a query. And the answer is "yes". So this means that every word that matches the target pattern must begin with 0. So the first symbol of the target pattern is 0, and we'll do the same for each other variable. So, can we replace y by 0? No. Then maybe we can replace it by 1. Yes, so it must be 1. So can we replace z by 0? Yes, good. And u by 0? No. By 1? Yes. Okay, v, can it be 0? No. 1? No, okay, so we get "no" both times, when we replaced u by 0 and when we replaced u by 1. This means that our language, the target language, contains words that have 0 at the fifth position and also those that have 1 at the fifth position. So this must be a variable, not any constant. What about w? Can we replace it by 0? Yes. What about s? Can we replace it by 0? No. Maybe, by 1? And again no, so this as a variable. What about t? 0? No! 1? No! So, again it's a variable. And that's how our pattern looks like. It has, it consists of eight symbols. Five of them are constants and we know which constants. And three are variables. All that remains is to find out whether some of these variables are the same. Here we have u, s, and t as different variables. But maybe some of them in the target pattern are identical. Let's replace s by u and see if it works. Yes, this works. When we replace s by u, the restriction that we put on the language is that they, this variable, u, and this variable, formerly known as s, must be replaced by the same substring, and so it must be the same variable. And let's do the same for t. Can we replace t by u? The answer is "no". This means that the language contains words obtained from this pattern where u is replaced by one string and t is replaced by some other string. So that's the final pattern guessed by the oracle. Let's check this. We'll submit the equivalence query using the pattern we've just computed. And the answer is "yes". So that's the true pattern guessed by our oracle. Let's summarise our algorithm. It has three parts. First we determine the length k of the pattern using only k superset queries. And we can even do it more efficiently if we use binary search. Then we determine all the constants of our pattern using at most 2k superset queries. Finally, we find out which of the variables are identical, and this requires less than k^2 superset queries. Thus we get an algorithm that needs time polynomial in the length of the target pattern. This algorithm uses only superset queries. And note that it doesn't even need counterexamples provided by the oracle. It is possible to use counterexamples to speed up things a little bit, but we can also do without them. [NOISE] [MUSIC]