Polynomial Identification of $\omega$-Automata
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Anzahl der Teile | 22 | |
| Autor | ||
| Lizenz | CC-Namensnennung 3.0 Deutschland: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. | |
| Identifikatoren | 10.5446/55019 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Schlagwörter |
00:00
Familie <Mathematik>Relation <Informatik>DatenstrukturPolynomPolynomSystemidentifikationAutomat <Automatentheorie>ProgrammierparadigmaWort <Informatik>Inverser LimesDeterministischer endlicher AutomatPhysikalisches SystemFormale GrammatikAuswahlaxiomTypentheorieMehrrechnersystemFormale SpracheSchnittmengeFamilie <Mathematik>ProgrammverifikationGerade ZahlAggregatzustandSoftwareschwachstelleGrenzwertberechnungKonditionszahlNichtunterscheidbarkeitAbfrageDeterministischer ProzessElement <Gruppentheorie>TeilmengeLeistung <Physik>Reguläre SpracheRelativitätstheorieÄquivalenzklasseKlasse <Mathematik>Übersetzer <Informatik>GrenzschichtablösungAlgorithmusCharakteristisches PolynomInteraktives FernsehenUnendlichkeitEigentliche AbbildungBitZweiCASE <Informatik>TermSignifikanztestKomplex <Algebra>Lokales MinimumSelbstrepräsentationTabelleDatenstrukturFunktion <Mathematik>InjektivitätLogischer SchlussQuick-SortRechter WinkelMultiplikationsoperatorMengensystemKongruenzuntergruppeNummernsystemEinfach zusammenhängender RaumZahlenbereichEndliche ModelltheorieTransitivitätRegulärer GraphFinitismusEinsAnalysisIsomorphieklasseEndlichkeitResultanteAssoziativgesetzTopologieKategorie <Mathematik>Wald <Graphentheorie>ÄhnlichkeitsgeometrieDifferenteModallogikOrdnung <Mathematik>Mapping <Computergraphik>GraphfärbungBereichsschätzungKreisflächeBildschirmmaskeComputeranimation
Transkript: Englisch(automatisch erzeugt)
00:00
Hello, everybody. I'm going to present this work about polynomial identification of omega automata. I'm Dana Fissman, and this is a joint work with Dana Englemann and Yara Shubair. So this work concerns automata learning and verification. This is also called model learning, and this is the question of inferring a system by observing a black-box system, the behaviors,
00:23
the input-output behaviors. Automata learning basically refers to classified to two different paradigms. One is called active learning, and the other one is passive learning. In the passive learning approach, the learner is exhibiting a set of labeled words,
00:42
and it should produce an automaton that agrees with a given set of words. So those that are labeled positively are in the language, and those that are labeled negatively are not in the language. In the active learning, the learner interacts with a teacher, also called an oracle, which is familiar with the target language
01:01
by asking it several types of queries, and the teacher always answers truthfully. After a finite number of queries, the learner should be able to produce an automaton that correctly recognizes the unknown target language.
01:21
So in the background, we have a class of languages L, the target language is one of these classes, and we also have in the background the class of acceptance A, the output automata should be in this class. This class should be able to represent all the languages
01:41
in the assumed given class of languages. And representation, of course, matters. So for instance, regular languages are known to have many different formalisms, all recognizing exactly the real languages. And when we are asking whether they are learnable under a certain type of paradigm,
02:01
then it depends which formalism we consider. So for instance, DFA's can be polynomially learned using membership queries and equipment queries, whereas NFA's cannot. In this work, we are concerned with omega automata. These are all automata that accept infinite words,
02:23
and we are concerned with omega automata since your reactive systems that are basically used in verification concerns automata under infinite words. So one of the first questions to come to mind is how do we represent infinite words? How do we finally represent them?
02:42
So the answer is that we work with ultimately periodic words. These are words of the form u and v to the omega. And the reason is that two omega regular languages are equivalent if and only if they agree on a set of ultimately periodic words. So this choice shouldn't limit the power of interference.
03:03
So what can I tell you about the state of the art of omega automata learning? So in the active learning, one of the first positive results was by Maler and Poulet from 1995, which showed that deterministic weak parity automata are polynomially learnable using proper membership
03:21
queries and equivalence queries. If we would like to learn all the omega regular languages, we can do so using a representation called the families of VFA's. So all the omega regular languages are learnable using this representation,
03:43
but the learned algorithm is not necessarily run in polynomial time. Another formalism which is good to learn in all the omega regular languages are SUBA's Strongly Anamised Lucio Tonta,
04:02
for which we have shown a polynomial learnable algorithm with membership queries and nonproperly lenient queries. In the passive learning, there aren't any results that we know of, and this is where we come in. So the exact paradigm that we consider in passive learning
04:23
is termed identification limit using polynomial time and data. So to be more precise, we would say that a class of acceptors n, recognizing a class of languages l, is identifiable in the limit using polynomial time and data if certain requirements are met, and these
04:41
are the requirements. So the first requirement is the usual passive learning requirement, given a labeled set of words, the algorithm with fears and automaton that agrees with the word, but this is strengthened to require that this is done in polynomial time.
05:00
The more interesting requirement is the requirement that will allow us to obtain not only an automaton that agrees with a certain set of words, but with one of the languages in our class of languages. So given the class, any language in our class of languages, we would like to be able to generate a set of words,
05:23
self-labeled words, w, l, that agrees with l, of course, and is of size polynomial in names. We get polynomial data where the size of l is measured as the size of the smallest acceptor for a. And this set should be helpful for the inference
05:43
algorithm to return an automaton for l. So to be more precise, the requirement is that given this set w, l, which we term the characteristic set for l, the learning algorithm is able to infer an automaton that
06:01
recognizes l, right? So not the strongest requirement. Not only this automaton should agree with w, l, it should agree, it should recognize l. So it should agree with every word in n, whether it's in one of the third words or it is not.
06:20
And moreover, the algorithm shouldn't be fooled if it is given any set of words, w prime, that subsumes w, l. So as mentioned, w, l is termed the characteristic set for l. So the results that we show in the paper is on the negative side that the classes of languages
06:43
of non-deterministic mu-ki automata, non-deterministic parity automata, monor or co-mochi automata are not identifiable using polynomial time and data. I won't have the time to get into this result in this presentation. And the positive result is that a certain class,
07:02
that four classes which I will define shortly, but I call them isomorphic mu-ki, isomorphic parity, isomorphic motor, and isomorphic commonware are identifying the limit using polynomial time and data. And on the way to obtain this positive result will be the data result, which
07:21
might be of independent interest, which associates with every deterministic parity automaton a certain canonical forest that has some interesting properties. OK, so in order to explain what are the languages, i, b, i, c, i, p, i, m, that we consider in this work,
07:41
which we obtain with a positive result, I would like to recall a difference between regular and non-regular languages. So for regular languages, it is known that there is a one-to-one relation between the number of states of the minimum DFA and the equivalence classes of the right congruence relation for L.
08:02
The right congruence relation for L is defined as congruence. So two finite words are said to be congruent to one another with respect to L, if they have low-distinction suffix, meaning that for every finite word z, x concatenated to z is in the language, if and only if y concatenated to z is in the language.
08:22
So to take an example, we have a regular language of all the words that end with at least one b. And this language can be recognized by the following DFA with two states. And if we compute the equivalence classes of this right congruence relation,
08:40
then we end up with two equivalence classes. One is the words that end with an a, which exactly corresponds to this state of the DFA. And the other one is all the words that end with a b, which exactly corresponds to this state of the DFA. So we have this one-to-one relationship
09:02
between the states of the minimum DFA and the equivalence classes of the right congruence relation. Now, if we go to the omega regular case, if we consider the termistic molar automata or any other omega automata that is used for regular languages, one of the common ones,
09:22
then there is no such one-to-one relationship. In fact, the right congruence relation for an omega language L is not informative enough to infer all the states of a minimum automata from the language. So let's first pause and see how
09:41
the right congruence relation is defined for omega languages. So the definition is pretty much the same, only that instead of considering finite words for suffixes, we consider infinite words for suffixes. So if we now look at a very similar language, but which is an omega language,
10:02
we can think about the language which has the omega as a suffix, okay? So then we can construct the minimal DMA, a minimal DMA for this language. This is a minimal DFA for the language. It accepts all the words which have a b omega as a suffix.
10:20
Now, if we compute the equivalence classes of the right congruence relation, we end up with just one equivalence class. And this is in no two words and a distinguishing suffix. If you take any word and concatenate to it, some infinite word,
10:41
if this infinite word has b omega as a suffix, then the concatenation would be L no matter which word you took, X or Y. And if Z doesn't have b omega as a suffix, then whether you concatenate it to any word X or Y,
11:01
it wouldn't be in the language. So we have just one equivalence class, and clearly we cannot have one-to-one relation between two states and one equivalence class. So this is where the classes of languages, IB, IP, IM and IC come into the picture. And so what is exactly the definition of IB?
11:23
So IB is the class of languages N where there is a one-to-one relation between the classes of the equivalence relation tilde L and the number of states in the minimal deterministic book U-ton-ton for M.
11:41
And the class IC is defined similarly but considering the deterministic comorbidity automata, IP considering the deterministic parity automata, and IM considering the deterministic comorbidity automata. So these are what we call the isomorphic classes.
12:01
So it is known that these subset relations hold from these classes. And what is more interesting is they don't know without this restriction of the deterministic classes to the ones that are isomorphic to the right congruence class sounds very limiting.
12:21
In fact, you can find languages in these classes which are as arbitrary, as complex as one would like. If we measure the complexity in terms of the infinite Wagner hierarchy, then in every class of the Wagner hierarchy, there exists a language which is both in IM and in IP.
12:42
Okay, so what we would like to do now is show that these set of classes can be identified in the limit using polynomial timing data. So we have to show that these requirements of polynomial identification are satisfied.
13:01
So let's start with the requirement of constructing a characteristic set. So given a set of languages, given a set, given LL language, we know that we have an automaton for it, an automaton in one of these classes, which is isomorphic to the right congruence relation.
13:20
And we obtain our characteristic set from the automaton. We actually obtain the characteristic set in two steps. In step one, we collect the set of words that will help the algorithm infer the structure of the automaton. In step two, we construct a set of words that would help the algorithm
13:41
infer the acceptance condition of the automaton. And the union of these two would be the characteristic set for LL. So the structure of the automaton is the same in all of the classes that we consider, IB, IC, IP, and IM.
14:00
The acceptance condition differs according to the class that we consider. So we have one way to constructing these words for IM and another way to constructing these words for IP. And IB and IC can be seen as a special case of IP.
14:21
The second thing that we need to show is once we have these characteristic set or we don't have that the inference algorithm produces the set which correctly recognizes LL or just agrees with the set of language and runs in polynomial time. So the scheme for doing this is as follows.
14:41
So given the given asset of learning words, the algorithm optimistically assumes that it contains a characteristic set that we are in this part. And it tries to use this set to infer the structure of the automaton. And from the words and the structure,
15:01
it tries to obtain the acceptance condition of the automaton. And if this works well, then it actually obtain the full access to a full automaton for the language. But if W doesn't subsume a characteristic set where in this case,
15:21
then the acceptance, inferring the acceptance condition probably wouldn't work. And in this case, the algorithm resorts to returning an automaton which we call the table lookup for the given set of words. Okay, so let me share a little bit about how we construct the characteristic set
15:42
for sort of starting with the words that help the algorithm infer the structure of the automaton. So this is the same for all the classes we consider. If we are given a certain type of automaton, we want to find a prefix closed set of access words words
16:00
that reach each state of the automaton. So here we can choose epsilon A, ABAA and AAB. This is a prefix closed set that reaches every state of the automaton. And we call this set S. Now given S in the second step, we would like to find a distinction word
16:21
for each distinct pair of access words. So we can create this table and for each pair of distinct access words, we can look for a word that distinguishes them. So it should take one to an accepted state and the other one not. So for instance, if we consider epsilon and A,
16:42
then the word A is a legitimate distinguishing suffix and it takes A epsilon to an accepting state and it doesn't take A to an accepting state. So after filling all the table, we get a set which we call E of distinguishing words.
17:01
And the set of label words W struct is constructed as follows. So it consists of the words S concatenated to E as well as the word S concatenated to C concatenated to E. From this, the learning algorithm should interfere
17:23
the states of the automaton and from this, the transition relation of the automaton. So now we can ask ourselves how we construct a set of label words that would help the algorithm with the acceptance condition. And let's start with the case of modal automaton.
17:42
So in a modal automaton, the acceptance condition is given via a set of sets of states, which are marked here in the green circles. So what the algorithm does, it takes one of these sets, if I for instance, and finds for it more the W I
18:00
such that the states that are visited infinitely often when reading W I is exactly F I. So for instance, if we consider the set consisting of two and three, then the word A be a omega, A satisfies the requirements that you want, it visits exactly two and three infinitely often.
18:23
So the set W I contains exactly one word for every accepting set. So the number of accepting sets might be exponentially the number of states of the DMA, but still the size of WX set
18:42
is polynomial in the size of the modal automaton since the size of the modal automaton doesn't take into consideration only the number of states, but also the size of the acceptance condition and we are polynomial in that. So we would like to do something similar
19:02
for a parity automaton where parity automata are, in a parity automaton the acceptance condition is given via a color ring, which maps every state to some number. And the question is how we do that. So what matters in omega automata
19:21
are the words that we visit infinitely often or the set of states that we visited infinitely often. Which are the strongly connected, which are all strongly connected components of the given automaton. And now doing an analysis on all the strongly connected components of the automaton is a bit problematic
19:40
because there are an exponential number of strongly connected components in the automaton. And now we wouldn't be able to claim that this is polynomial in the given DPA to a separate automaton. So we need to do something a little bit more clever. And for this we use the theorem, which associates with every parity automaton
20:03
economical forest, which is inspired by the Sri Lanka tree. And it sharpens the situation when we start with a parity automaton. So it won't be able to get into all these, the nice properties of this forest, but I will mention that it has at most a Q nodes
20:25
and it can be computed in polynomial time. So now when we are giving a deterministic parity automaton, we can construct in polynomial time, the forest for this automaton
20:40
and from the forest of this automaton, which has at most Q nodes and each node corresponds to one of the strongly connected components of the automaton, we can construct a set of words as follows. So for every node, we consider as in the previous case,
21:00
a word that visits all the states in that nodes, in that node here, if we want to visit four and five infinitely often, we can take word A, A, B, B omega, which is A, B omega.
21:21
And the set W accept would consist of one word for each node of the forest. And since the number of nodes in the forest is bounded by the number of states, this is polynomial in the given deterministic parity automaton. So unfortunately I don't have the time
21:40
to share some of the ideas in inferring the structure or in inference, the acceptance condition for molar or for parity, but you can find all the details in the paper. So to conclude in the paper, we show that the classes, non-deterministic classes of bookie, parity, molar
22:01
and co-bookie are not identifiable in the polynomial time data, but we show that the isomorphic classes, these are the restriction of the deterministic classes to those that are isomorphic to the right confidence relation are identifiable in the limit using polynomial time data. And what remains open is the question
22:21
whether the deterministic classes without this restriction are identifiable in the limit using polynomial time data. So I guess it's time for questions now. Thank you.