Package de.learnlib.algorithm.rpni

Class 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:
    BlueFringeEDSMDFA, BlueFringeMDLDFA, BlueFringeRPNIDFA, BlueFringeRPNIMealy, BlueFringeRPNIMoore
    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.

    • Field Detail

      • alphabet

        protected final Alphabet<I> alphabet

      • alphabetSize

        protected final int alphabetSize

    • Constructor Detail

      • AbstractBlueFringeRPNI

        public AbstractBlueFringeRPNI​(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

      • setProcessingOrder

        public void setProcessingOrder​(ProcessingOrder order)
        Sets the order in which the respective merge candidates should be processed.
        Parameters:
        order - the order

      • computeModel

        public M computeModel()
        Description copied from interface: PassiveLearningAlgorithm
        Computes the model given the previously added samples.

        Implementation note: It is up to the implementation if this operation is repeatable or not, An implementation may throw an IllegalStateException if additional samples are added after the first model construction.

        Specified by:
        computeModel in interface PassiveLearningAlgorithm<I,​D,​SP>
        Returns:
        the computed model

      • fetchPTA

        protected abstract BlueFringePTA<SP,​TP> fetchPTA()
        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.
        Returns:
        the PTA for model construction.

      • 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