Package de.learnlib.algorithm.rpni

Class BlueFringeEDSMDFA<I>

java.lang.Object

de.learnlib.algorithm.rpni.AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,DFA<?,I>>

de.learnlib.algorithm.rpni.BlueFringeEDSMDFA<I>

Type Parameters:

I - input symbol type

All Implemented Interfaces:

PassiveLearningAlgorithm<DFA<?,I>,I,Boolean>, PassiveLearningAlgorithm.PassiveAcceptorLearner<DFA<?,I>,I>, PassiveLearningAlgorithm.PassiveDFALearner<I>

public class BlueFringeEDSMDFA<I>
extends AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,DFA<?,I>>
implements PassiveLearningAlgorithm.PassiveDFALearner<I>

A state-merging learning algorithm based on the evidence 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 EDSM variant prioritizes the promotion of states (to be unmergable) and only proceeds to merge states, if there exists at least one mergable blue state for every red state. If such a situation occurs, the algorithm merges the two states whose merge would yield the biggest score (see EDSMUtil.score(UniversalDeterministicAutomaton, List, List)). Thus, the behavior of this algorithm is more passive, or as the name suggest evidence-driven.

Implementation note: This implementation does support repeated calls to PassiveLearningAlgorithm.computeModel().

Nested Class Summary

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

PassiveLearningAlgorithm.PassiveAcceptorLearner<M extends FiniteStateAcceptor<?,I>,I>, PassiveLearningAlgorithm.PassiveDFALearner<I>, PassiveLearningAlgorithm.PassiveMealyLearner<I,O>, PassiveLearningAlgorithm.PassiveMooreLearner<I,O>

Field Summary

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

alphabet, alphabetSize

Constructor Summary

Constructors

Constructor	Description
BlueFringeEDSMDFA(Alphabet<I> alphabet)	Constructor.

Method Summary

Modifier and Type	Method	Description
void	addSamples(Collection<? extends DefaultQuery<I,Boolean>> samples)
protected BlueFringePTA<Boolean,Void>	fetchPTA()	Fetches the initial PTA for model construction.
protected DFA<?,I>	ptaToModel(BlueFringePTA<Boolean,Void> pta)	Transforms the final PTA into a model.
protected Stream<RedBlueMerge<BlueFringePTAState<Boolean,Void>,Boolean,Void>>	selectMerges(Stream<RedBlueMerge<BlueFringePTAState<Boolean,Void>,Boolean,Void>> merges)	Implementing the method allows subclasses to decide on (and possibly reject) valid merges.

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

computeModel, setDeterministic, setParallel, setProcessingOrder, 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.algorithm.PassiveLearningAlgorithm

addSample, addSample, addSamples, addSamples, addSamples, computeModel

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

addNegativeSample, addNegativeSamples, addNegativeSamples, addPositiveSample, addPositiveSamples, addPositiveSamples

Constructor Detail

BlueFringeEDSMDFA

public BlueFringeEDSMDFA(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<DFA<?,I>,I,Boolean>

fetchPTA

protected BlueFringePTA<Boolean,Void> fetchPTA()

Description copied from class: AbstractBlueFringeRPNI

Fetches the initial PTA for model construction. If subclasses need to cache the training data this may be a fresh instance. If subclasses directly insert training data to a local PTA, they should make sure that repeated invocations of this method are not possible.

Specified by:

fetchPTA in class AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,DFA<?,I>>

Returns:

the PTA for model construction.

selectMerges

protected Stream<RedBlueMerge<BlueFringePTAState<Boolean,Void>,Boolean,Void>> selectMerges(Stream<RedBlueMerge<BlueFringePTAState<Boolean,Void>,Boolean,Void>> merges)

Description copied from class: AbstractBlueFringeRPNI

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

Overrides:

selectMerges in class AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,DFA<?,I>>

Parameters:

merges - the prosed (valid) merges

Returns:

the merges that should be considered for selecting a merge.

ptaToModel

protected DFA<?,I> ptaToModel(BlueFringePTA<Boolean,Void> pta)

Description copied from class: AbstractBlueFringeRPNI

Transforms the final PTA into a model.

Specified by:

ptaToModel in class AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,DFA<?,I>>

Parameters:

pta - the final PTA

Returns:

a model built from the final PTA