about GenericObservationTable

[guo guo]

Hello, I want to build a model about L * algorithm. For the OT table, do you have to pass in a complete automata to generate the OT table? Because I see that in the example, a complete automaton is introduced.

Looking forward to your reply, thank you!

[Markus Frohme]

Dear Guo,


yes, most active learning algorithms (including L*) construct complete hypotheses and require the membership oracle to answer queries for all posible words over the given alphabet. However, you can also handle partially defined systems under learning when you fallback to some default behavior in these cases.

For example, if a DFA can no longer transition to a state upon reading an input (undefined transition) the word will be rejected. So in a membership oracle you could simply return "false". This will then result in a sink state in the hypothesis which collects all undefined transitions.

Similarly for Mealy machines, you can (repeatedly) emit a special "undefined" output symbol which will then also result in a "undefined" sink.


Kind regards,
Markus

> --
> You received this message because you are subscribed to the Google Groups "LearnLib Q&A" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to learnlib-qa...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/learnlib-qa/a182b6f8-1a87-49a2-83e3-295b57b11d06n%40googlegroups.com.

[guo guo]

Thank you for your last answer, but I have another question. Instead of CompactDFA< character >, I rewritten the answerquery of MQ and directly used DFAwmethodeqOracle. Why won't the OT table be generated after running? Will not generate the graph of automata?But I set EXPLORATION_DEPTH is 2, I run two rounds and find two counterexamples. Why doesn't the program stop running like the example?  EXPLORATION_DEPTH   means that the operation ends after two rounds of operation?

Thanks again!

[Markus Frohme]

Dear Guo,


the W-method uses a combination of transition coverage and (state-) characterizing set to construct tests. Our implementation allows for an additional "exploration sequence" to account for the fact that especially in the beginning, the hypotheses are small and therefore the W-method may not generate a sufficient amount of test cases. Our oracle constructs cases based on the cross product of "transition coverage x exploration x characterizing set" and the EXPLORATION_DEPTH is the length of the "exploration" sequences. Note that we use all combinations of input symbols, so the number of testcases grows exponentially in the parameter.

Regarding your problem of not terminating: Are you able to get intermediate hypotheses or does the "startLearning" call already not return? Usually, this is a problem, when your system abstraction is not regular, e.g. when you are counting something. For every +1 you are able to do a -1, so in theory you would get an infinitely long list of states, which is why the process doesn't terminate. If you can explain what kind of system you are trying to learn, maybe we can provide more advice.


Kind regards,
Markus

> To view this discussion on the web visit https://groups.google.com/d/msgid/learnlib-qa/1526edfc-6a54-459e-a33f-be6b1c8077a2n%40googlegroups.com.

[guo guo]

Dear Markus,

I enter 0 and / or two symbols，Here is my rewritten answerquery：

@Override

public Boolean answerQuery(Word<I> prefix, Word<I> suffix) {

// TODO Auto-generated method stub

Word<I> concatWords = prefix.concat(suffix)；

}

DFAMembershipOracle<Character> sul = new LAMQ();

DFACounterOracle<Character> mqOracle = new DFACounterOracle<>(sul, "membership queries");

LAMQ

Then I pass concatwords into my defined membershipOracle(LAMQ)  to judge whether it is ture or false. But why does it keep running? And the final prefix is only ε.

Thank you，

Guo

[guo guo]

Dear Markus,

Surprisingly, I can generate the model, but there will be some errors. The initial state of the generated model does not have "→", and there will be many termination states. The model is very chaotic and will report " n.a.visualization.dot.DOT - Error executing dot
java.io.IOException: Cannot run program "dot": CreateProcess error=2,”errors. Why? Thank you very much!

Kind regards,

Guo

[Markus Frohme]

Dear Guo,


regarding your first e-mail: I don't think I quite understood the whole situation. One the one hand you write that the process keeps running, but on the other hand you are able to see a final prefix epsilon? So it is possible to construct an initial hypothesis but the refinement after the first refinement results in an infinite loop?

Maybe you can add some debug outputs to you LAMQ class to see if it is actually a infinite loop or some problem with your SUL answering the queries. This should give a direction for further analyzing the issue.


Regarding your second e-mail: This looks to me that you don't have the DOT binary available in your shell environment. You either have to setup your PATH variable correclty or you can explicitly set the path to the DOT installation/executable via JVM properties [0,1]. The visualization in your picture is the (fallback) JUNG visualizer, which unfortunately has no support for auto-layouting.


Kind regards,
Markus

[0] - https://github.com/LearnLib/automatalib/blob/develop/api/src/main/java/net/automatalib/AutomataLibProperty.java#L26
[1] - https://github.com/LearnLib/automatalib/blob/develop/api/src/main/java/net/automatalib/AutomataLibProperty.java#L33

[guo guo]

Dear Markus,

Thank you very much for your answer, which is very helpful to me!

kind regards,

Guo