de.learnlib.algorithms.rpni

Class AbstractBlueFringeRPNI<I,D,SP,TP,M>

java.lang.Object

de.learnlib.algorithms.rpni.AbstractBlueFringeRPNI<I,D,SP,TP,M>

Type Parameters:

I - input symbol type

D - output domain type

SP - state property type

TP - transition property type

M - model type

All Implemented Interfaces:

PassiveLearningAlgorithm<M,I,D>

Direct Known Subclasses:

BlueFringeRPNIDFA, BlueFringeRPNIMealy

public abstract class AbstractBlueFringeRPNI<I,D,SP,TP,M>
extends Object
implements PassiveLearningAlgorithm<M,I,D>

Abstract base class for Blue-Fringe-RPNI algorithms.

Unlike most descriptions of RPNI in the literature, the Blue Fringe version of RPNI does not consider all possible pairs of states for merging, but instead maintains a monotonically growing set of "red states", the immediate non-red successors of which are called blue states. In each iteration of the main loop, an attempt is made to merge a blue state into any red state. If this is impossible, the blue state is promoted, meaning it is converted into a red state itself. The procedure terminates when all states are red.

A blue fringe version of RPNI is described in the book "Grammatical Inference" by Colin de la Higuera.

Author:

Malte Isberner

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

Modifier and Type	Field and Description
protected net.automatalib.words.Alphabet<I>	alphabet
protected int	alphabetSize
protected boolean	deterministic
protected ProcessingOrder	order
protected boolean	parallel

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
M	computeModel()
protected boolean	decideOnValidMerge(RedBlueMerge<SP,TP,BlueFringePTAState<SP,TP>> merge) Implementing the method allows subclasses to decide (and possible reject) valid merges.
protected abstract void	initializePTA(BlueFringePTA<SP,TP> pta) Initializes an empty PTA with sample data.
protected abstract M	ptaToModel(BlueFringePTA<SP,TP> pta) Transforms the final PTA into a model.
void	setDeterministic(boolean deterministic) Sets whether the outcome of the algorithm is required to be deterministic (i.e., subsequent calls of computeModel() on the same input data will perform the same merges and return the same result).
void	setParallel(boolean parallel) Sets whether attempts to merge a blue into a red state are conducted in parallel.
protected RedBlueMerge<SP,TP,BlueFringePTAState<SP,TP>>	tryMerge(BlueFringePTA<SP,TP> pta, BlueFringePTAState<SP,TP> qr, BlueFringePTAState<SP,TP> qb) Attempts to merge a blue state into a red state.

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

addSample, addSample, addSamples, addSamples, addSamples, addSamples

Field Detail

alphabet

protected final net.automatalib.words.Alphabet<I> alphabet

alphabetSize

protected final int alphabetSize

order

@Nonnull
protected final ProcessingOrder order

parallel

protected boolean parallel

deterministic

protected boolean deterministic

Constructor Detail

AbstractBlueFringeRPNI

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

Constructor.

Parameters:

alphabet - the alphabet

Method Detail

setParallel

public void setParallel(boolean parallel)

Sets whether attempts to merge a blue into a red state are conducted in parallel.

Note that setting this to true does not inhibit the possibility of deterministic algorithm runs (see setDeterministic(boolean)).

Parameters:

parallel - whether to parallelize the process of finding a possible merge

setDeterministic

public void setDeterministic(boolean deterministic)

Sets whether the outcome of the algorithm is required to be deterministic (i.e., subsequent calls of computeModel() on the same input data will perform the same merges and return the same result).

Note that if parallel execution is disabled (see setParallel(boolean)), the algorithm will most likely (but is not required to) behave deterministically even with this set to false. However, if parallelization is enabled, results of subsequent invocations will most likely differ with this parameter set to false.

Parameters:

deterministic - whether to enforce deterministic algorithm behavior

computeModel

public M computeModel()

Specified by:

computeModel in interface PassiveLearningAlgorithm<M,I,D>

initializePTA

protected abstract void initializePTA(BlueFringePTA<SP,TP> pta)

Initializes an empty PTA with sample data.

Parameters:

pta - the PTA to initialize

tryMerge

protected RedBlueMerge<SP,TP,BlueFringePTAState<SP,TP>> tryMerge(BlueFringePTA<SP,TP> pta,
                                                                 BlueFringePTAState<SP,TP> qr,
                                                                 BlueFringePTAState<SP,TP> qb)

Attempts to merge a blue state into a red state.

Parameters:

pta - the blue fringe PTA

qr - the red state (i.e., the merge target)

qb - the blue state (i.e., the merge source)

Returns:

a valid RedBlueMerge object representing a possible merge of qb into qr, or null if the merge is impossible

ptaToModel

protected abstract M ptaToModel(BlueFringePTA<SP,TP> pta)

Transforms the final PTA into a model.

Parameters:

pta - the final PTA

Returns:

a model built from the final PTA

decideOnValidMerge

protected boolean decideOnValidMerge(RedBlueMerge<SP,TP,BlueFringePTAState<SP,TP>> merge)

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

Parameters:

merge - the prosed (valid) merge

Returns:

true if the suggested merge should be performed, false otherwise