Package net.automatalib.util.minimizer

Class Minimizer<S,​L>

  • Type Parameters:
    S - state class.
    L - transition label class.
    public final class Minimizer<S,​L>
extends Object
    Automaton minimizer. The automata are accessed via the UniversalGraph interface, and may be partially defined. Note that undefined transitions are preserved, thus, they have no semantics that could be modeled otherwise wrt. this algorithm.

    The implemented algorithm is described in the paper Minimizing incomplete automata by Marie-Pierre Beal and Maxime Crochemore.

    • Constructor Detail

      • Minimizer

        public Minimizer()

    • Method Detail

      • minimize

        public static <S,​L> MinimizationResult<S,​L> minimize​(UniversalGraph<S,​?,​?,​L> graph)
        Minimizes an automaton. The automaton is not minimized directly, instead, a MinimizationResult structure is returned. The automaton is interfaced using an adapter implementing the UniversalGraph interface.
        Type Parameters:
        S - state class.
        L - transition label class.
        Parameters:
        graph - the automaton interface.
        Returns:
        the result structure.

      • performMinimization

        public <E> MinimizationResult<S,​L> performMinimization​(UniversalGraph<S,​E,​?,​L> graph,
                                                             Collection<? extends S> initialNodes)
        Performs the minimization of an automaton.

        The automaton is accessed via a UniversalGraph. The result of the minimization process is effectively a partition on the set of states, each element (block) in this partition contains equivalent states that can be merged in a minimized automaton.

        Type Parameters:
        E - edge identifier class.
        Parameters:
        graph - the automaton interface.
        Returns:
        a MinimizationResult structure, containing the state partition.