Package net.automatalib.incremental.mealy.tree

Class DynamicIncrementalMealyTreeBuilder<I,​O>

  • Type Parameters:
    I - input symbol type
    O - output symbol type
    All Implemented Interfaces:
    SupportsGrowingAlphabet<I>, IncrementalConstruction<MealyMachine<?,​I,​?,​O>,​I>, IncrementalMealyBuilder<I,​O>, MealyBuilder<I,​O>
    public class DynamicIncrementalMealyTreeBuilder<I,​O>
extends Object
implements IncrementalMealyBuilder<I,​O>
    A variation of the normal IncrementalMealyTreeBuilder which stores the successor information of each tree-node in a dynamically allocated Map.

    In a dense tree-structure this may result in higher memory consumption than the regular tree. However, if only sparse information are stored, the overall consumption may be lower. Also, allows to skip the initial alphabet definition as symbol information can be stored dynamically and may us

    • Constructor Detail

      • DynamicIncrementalMealyTreeBuilder

        public DynamicIncrementalMealyTreeBuilder()

    • Method Detail

      • insert

        public void insert​(Word<? extends I> input,
                   Word<? extends O> outputWord)
        Description copied from interface: IncrementalMealyBuilder
        Incorporates a pair of input/output words into the stored information.
        Specified by:
        insert in interface IncrementalMealyBuilder<I,​O>
        Parameters:
        input - the input word
        outputWord - the corresponding output word

      • addAlphabetSymbol

        public void addAlphabetSymbol​(I symbol)
        Description copied from interface: SupportsGrowingAlphabet
        Notifies the data structure that a new symbol should be added to the alphabet. Behavior depends on the implementation:
        • After adding a new symbol, the symbol-related data may either be initialized with default values or undefined.
        • Duplicate symbols may: (1) be handled accordingly, (2) be ignored or (3) result in an error.
        Some data structures may need to be properly initialized (e.g. with a GrowingAlphabet) to handle potentially shared state across multiple instances. If the needed requirements are not met, a GrowingAlphabetNotSupportedException can be thrown.
        Specified by:
        addAlphabetSymbol in interface SupportsGrowingAlphabet<I>
        Parameters:
        symbol - the symbol to add to the alphabet.

      • asGraph

        public Graph<?,​?> asGraph()
        Description copied from interface: IncrementalConstruction
        Retrieves a graph view of the current state of the construction. The graph model should be backed by the construction, i.e., subsequent changes will be reflected in the graph model.
        Specified by:
        asGraph in interface IncrementalConstruction<I,​O>
        Returns:
        a graph view on the current state of the construction

      • lookup

        public boolean lookup​(Word<? extends I> word,
                      List<? super O> output)
        Description copied from interface: MealyBuilder
        Retrieves the output word for the given input word. If no definitive information for the input word exists, the output for the longest known prefix will be returned.
        Specified by:
        lookup in interface MealyBuilder<N,​I>
        Parameters:
        word - the input word
        output - a consumer for constructing the output word
        Returns:
        true if the information contained was complete (in this case, word.length() == output.size() will hold), false otherwise.

      • findSeparatingWord

        public @Nullable Word<I> findSeparatingWord​(MealyMachine<?,​I,​?,​O> target,
                                            Collection<? extends I> inputs,
                                            boolean omitUndefined)
        Description copied from interface: IncrementalConstruction
        Checks the current state of the construction against a given target model, and returns a word exposing a difference if there is one.
        Specified by:
        findSeparatingWord in interface IncrementalConstruction<N,​I>
        Parameters:
        target - the target automaton model
        inputs - the set of input symbols to consider
        omitUndefined - if this is set to true, then undefined transitions in the target model will be interpreted as "unspecified/don't know" and omitted in the equivalence test. Otherwise, they will be interpreted in the usual manner (e.g., non-accepting sink in case of DFAs).
        Returns:
        a separating word, or null if no difference could be found.

      • asTransitionSystem

        public MealyTransitionSystem<?,​I,​?,​O> asTransitionSystem()
        Description copied from interface: IncrementalConstruction
        Retrieves a transition system view of the current state of the construction. The transition system model should be backed by the construction, i.e., subsequent changes will be reflected in the transition system.
        Specified by:
        asTransitionSystem in interface IncrementalConstruction<N,​I>
        Specified by:
        asTransitionSystem in interface MealyBuilder<N,​I>
        Returns:
        a transition system view on the current state of the construction