Question About RPNI

[5angjun]

Hi, I'm Sangjun Park who is interested in your project.

When I go through your Project, there is a RPNI learning algorithm that can learn DFA with Positive and Negative Set.

However, i'm curious when use it for Mealy Machine, my question is that "Is it possible to define negative set in Mealy Machine?"
I mean in network packet trace, how can i define negative set of network trace?

And Can you give me a simple example for using RPNI algorithm?
I think there aren't good example for this.

Best Regards,
Sangjun Park

[mtf90]

Dear @5angjun,

RPNI defines a (greedy) state-merging framework in which the negative set can prevent state merges if they lead to inconsistencies with the remaining observations. You can easily see this effect when omitting the negative set: the resulting automaton will always be the 1-state all-acceptor.

How do these inconsistencies materialize with Mealy machines? As soon as the constructed automaton outputs something different than the training set, it exhibits inconsistent behavior (thus state merging was invalid). In a sense, you no longer have a distinct positive and negative set, but all traces contribute in deciding whether state merging is valid. The same holds for RPNI's Moore variant.

[5angjun]

Thanks for replying question.
It was really helpful answer.

By the way, there are mealy machine example for learning mealy machine automation with RPNI?

There are just an example for learning DFA.
Can you add an example for Learning Mealy Machine?
I have a trouble with convert DFA example to Mealy machine

Best,
SangJun Park

[mtf90]

Well, transforming a DFA into a Mealy machine isn't that straight-forward because a DFA has (boolean) state properties, whereas a Mealy machine only has transition properties (outputs). If you want to transform an acceptor into a transducer, a Moore machine (with boolean output alphabet) should be much more intuitive.

As for learning Mealy machines via RPNI, you just need to provide the corresponding Mealy traces, e.g.

public static void main(String[] args) {

    final Alphabet<Character> alphabet = Alphabets.characters('a', 'b');
    final PassiveMealyLearner<Character, Character> learner = new BlueFringeRPNIMealy<>(alphabet);

    learner.addSample(Word.fromString("aab"), Word.fromString("xxy"));
    learner.addSample(Word.fromString("baa"), Word.fromString("yzz"));

    final MealyMachine<?, Character, ?, Character> model = learner.computeModel();

    Visualization.visualize(model, alphabet, new Visualizer<>());
}

private static class Visualizer<N, E> extends DefaultVisualizationHelper<N, E> {

    private int id;

    @Override
    public boolean getNodeProperties(N node, Map<String, String> properties) {
        properties.put(NodeAttrs.LABEL, Integer.toString(id++));
        return true;
    }
}

(The visualizer is just for making the displayed model a little bit prettier)

[5angjun]

Thanks
This is what i want.😀