de.learnlib.algorithms.rpni

Class BlueFringeMDLDFA<I>

java.lang.Object

de.learnlib.algorithms.rpni.AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,net.automatalib.automata.fsa.DFA<?,I>>

de.learnlib.algorithms.rpni.BlueFringeRPNIDFA<I>

de.learnlib.algorithms.rpni.BlueFringeMDLDFA<I>

Type Parameters:

I - input symbol type

All Implemented Interfaces:

PassiveLearningAlgorithm<net.automatalib.automata.fsa.DFA<?,I>,I,Boolean>, PassiveLearningAlgorithm.PassiveAcceptorLearner<net.automatalib.automata.fsa.DFA<?,I>,I>, PassiveLearningAlgorithm.PassiveDFALearner<I>

public class BlueFringeMDLDFA<I>
extends BlueFringeRPNIDFA<I>

A state-merging learning algorithm based on the minimal description length principle. On an operational level this algorithm is very similar to the BlueFringeRPNIDFA algorithm. However, whereas the basic RPNI approach merges the very first pair of nodes that resemble a valid merge, the MDL variant computes an additional score and only commits to a merge, if the resulting hypothesis will yield a better score.

This passive approach to state-merging works better in scenarios where only positive training data is available. Hence, this algorithm only expect positive training data.

Author:

frohme

Nested Class Summary

Nested classes/interfaces inherited from interface de.learnlib.api.algorithm.PassiveLearningAlgorithm

PassiveLearningAlgorithm.PassiveAcceptorLearner<M extends net.automatalib.automata.fsa.FiniteStateAcceptor<?,I>,I>, PassiveLearningAlgorithm.PassiveDFALearner<I>, PassiveLearningAlgorithm.PassiveMealyLearner<I,O>, PassiveLearningAlgorithm.PassiveNFALearner<I>

Field Summary

Fields inherited from class de.learnlib.algorithms.rpni.BlueFringeRPNIDFA

negative, positive

Fields inherited from class de.learnlib.algorithms.rpni.AbstractBlueFringeRPNI

alphabet, alphabetSize, deterministic, order, parallel

Constructor Summary

Constructors

Constructor and Description
BlueFringeMDLDFA(net.automatalib.words.Alphabet<I> alphabet) Constructor.

Method Summary

Modifier and Type	Method and Description
void	addSamples(Collection<? extends DefaultQuery<I,Boolean>> samples)
protected boolean	decideOnValidMerge(RedBlueMerge<Boolean,Void,BlueFringePTAState<Boolean,Void>> merge) Implementing the method allows subclasses to decide (and possible reject) valid merges.

Methods inherited from class de.learnlib.algorithms.rpni.BlueFringeRPNIDFA

initializePTA, ptaToModel

Methods inherited from class de.learnlib.algorithms.rpni.AbstractBlueFringeRPNI

computeModel, setDeterministic, setParallel, tryMerge

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface de.learnlib.api.algorithm.PassiveLearningAlgorithm.PassiveAcceptorLearner

addNegativeSample, addNegativeSamples, addNegativeSamples, addPositiveSample, addPositiveSamples, addPositiveSamples

Methods inherited from interface de.learnlib.api.algorithm.PassiveLearningAlgorithm

addSample, addSample, addSamples, addSamples, addSamples, computeModel

Constructor Detail

BlueFringeMDLDFA

public BlueFringeMDLDFA(net.automatalib.words.Alphabet<I> alphabet)

Constructor.

Parameters:

alphabet - the alphabet

Method Detail

addSamples

public void addSamples(Collection<? extends DefaultQuery<I,Boolean>> samples)

Specified by:

addSamples in interface PassiveLearningAlgorithm<net.automatalib.automata.fsa.DFA<?,I>,I,Boolean>

Overrides:

addSamples in class BlueFringeRPNIDFA<I>

decideOnValidMerge

protected boolean decideOnValidMerge(RedBlueMerge<Boolean,Void,BlueFringePTAState<Boolean,Void>> merge)

Description copied from class: AbstractBlueFringeRPNI

Implementing the method allows subclasses to decide (and possible reject) valid merges.

Overrides:

decideOnValidMerge in class AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,net.automatalib.automata.fsa.DFA<?,I>>

Parameters:

merge - the prosed (valid) merge

Returns:

true if the suggested merge should be performed, false otherwise