net.automatalib.util.automata.minimizer.hopcroft

Class HopcroftMinimization

java.lang.Object

net.automatalib.util.automata.minimizer.hopcroft.HopcroftMinimization

public final class HopcroftMinimization
extends Object

Versions of Hopcroft's minimization algorithm for deterministic finite automata.

Hopcroft's algorithm is a special case of the Paige/Tarjan partition refinement algorithm (see PaigeTarjan) for the case of deterministic automata. Its running time is O(nk log n), where n is the size of the input DFA and k the size of the input alphabet.

Important note: Hopcroft's minimization algorithm works for complete automata only. If the automaton is partial, please use PaigeTarjanMinimization instead. If any method is invoked with a partial automaton as its argument, this will result in a IllegalArgumentException at runtime.

Note that the partition refinement step only calculates classes of equivalent states. However, minimization also requires pruning of states that cannot be reached from the initial states. Most methods in this class have a variable called pruningMode of type HopcroftMinimization.PruningMode that controls if and when pruning is performed: if the automaton to be minimized is known to be initially connected (i.e., it contains no unreachable states), pruning can be omitted completely (by specifying HopcroftMinimization.PruningMode.DONT_PRUNE) without impairing correctness. Otherwise, pruning can be chosen to be performed on the automaton to be minimized (HopcroftMinimization.PruningMode.PRUNE_BEFORE), or on the calculated state partition (HopcroftMinimization.PruningMode.PRUNE_AFTER). For methods that do not provide a pruningMode parameter, the default is HopcroftMinimization.PruningMode.PRUNE_AFTER.

Author:

Malte Isberner

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	HopcroftMinimization.PruningMode Allows for controlling how automata are pruned during minimization.

Method Summary

Modifier and Type	Method and Description
static <S,I,A extends DFA<S,I> & InputAlphabetHolder<I>> CompactDFA<I>	minimizeDFA(A dfa) Minimizes the given DFA.
static <S,I,A extends DFA<S,I> & InputAlphabetHolder<I>> CompactDFA<I>	minimizeDFA(A dfa, HopcroftMinimization.PruningMode pruningMode) Minimizes the given DFA.
static <I> CompactDFA<I>	minimizeDFA(DFA<?,I> dfa, Alphabet<I> alphabet) Minimizes the given DFA.
static <I> CompactDFA<I>	minimizeDFA(DFA<?,I> dfa, Alphabet<I> alphabet, HopcroftMinimization.PruningMode pruningMode) Minimizes the given DFA.
static <A extends MutableDFA<?,I>,I> A	minimizeDFA(DFA<?,I> dfa, Alphabet<I> alphabet, HopcroftMinimization.PruningMode pruningMode, AutomatonCreator<A,I> creator) Minimizes the given DFA.
static <S,I,T,O,A extends MealyMachine<S,I,T,O> & InputAlphabetHolder<I>> CompactMealy<I,O>	minimizeMealy(A mealy) Minimizes the given Mealy machine.
static <S,I,T,O,A extends MealyMachine<S,I,T,O> & InputAlphabetHolder<I>> CompactMealy<I,O>	minimizeMealy(A mealy, HopcroftMinimization.PruningMode pruningMode) Minimizes the given Mealy machine.
static <I,O> CompactMealy<I,O>	minimizeMealy(MealyMachine<?,I,?,O> mealy, Alphabet<I> alphabet) Minimizes the given Mealy machine.
static <I,O> CompactMealy<I,O>	minimizeMealy(MealyMachine<?,I,?,O> mealy, Alphabet<I> alphabet, HopcroftMinimization.PruningMode pruningMode) Minimizes the given Mealy machine.
static <A extends MutableMealyMachine<?,I,?,O>,I,O> A	minimizeMealy(MealyMachine<?,I,?,O> mealy, Alphabet<I> alphabet, HopcroftMinimization.PruningMode pruningMode, AutomatonCreator<A,I> creator) Minimizes the given Mealy machine.
static <I,T,SP,TP,A extends MutableDeterministic<?,I,?,SP,TP>> A	minimizeUniversal(UniversalDeterministicAutomaton<?,I,T,SP,TP> automaton, Alphabet<I> alphabet, AutomatonCreator<A,I> creator, AutomatonInitialPartitioning ap, HopcroftMinimization.PruningMode pruningMode) Minimizes the given automaton depending on the given partitioning function.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

minimizeDFA

public static <S,I,A extends DFA<S,I> & InputAlphabetHolder<I>> CompactDFA<I> minimizeDFA(A dfa)

Minimizes the given DFA. The result is returned in the form of a CompactDFA, using the input alphabet obtained via dfa.getInputAlphabet(). Pruning (see above) is performed after computing state equivalences.

Parameters:

dfa - the DFA to minimize

Returns:

a minimized version of the specified DFA

minimizeDFA

public static <S,I,A extends DFA<S,I> & InputAlphabetHolder<I>> CompactDFA<I> minimizeDFA(A dfa,
                                                                                          HopcroftMinimization.PruningMode pruningMode)

Minimizes the given DFA. The result is returned in the form of a CompactDFA, using the input alphabet obtained via dfa.getInputAlphabet().

Parameters:

dfa - the DFA to minimize

pruningMode - the pruning mode (see above)

Returns:

a minimized version of the specified DFA

minimizeDFA

public static <I> CompactDFA<I> minimizeDFA(DFA<?,I> dfa,
                                            Alphabet<I> alphabet)

Minimizes the given DFA. The result is returned in the form of a CompactDFA, and pruning (see above) is performed after computing state equivalences.

Parameters:

dfa - the DFA to minimize

alphabet - the input alphabet (this will be the input alphabet of the returned DFA)

Returns:

a minimized version of the specified DFA

minimizeDFA

public static <I> CompactDFA<I> minimizeDFA(DFA<?,I> dfa,
                                            Alphabet<I> alphabet,
                                            HopcroftMinimization.PruningMode pruningMode)

Minimizes the given DFA. The result is returned in the form of a CompactDFA.

Parameters:

dfa - the DFA to minimize

alphabet - the input alphabet (this will be the input alphabet of the returned DFA)

pruningMode - the pruning mode (see above)

Returns:

a minimized version of the specified DFA

minimizeDFA

public static <A extends MutableDFA<?,I>,I> A minimizeDFA(DFA<?,I> dfa,
                                                          Alphabet<I> alphabet,
                                                          HopcroftMinimization.PruningMode pruningMode,
                                                          AutomatonCreator<A,I> creator)

Minimizes the given DFA. The result is returned in the form of a CompactDFA.

Parameters:

dfa - the DFA to minimize

alphabet - the input alphabet (this will be the input alphabet of the returned DFA)

pruningMode - the pruning mode (see above)

creator - the creator for constructing the automata instance to return

Returns:

a minimized version of the specified DFA

minimizeMealy

public static <S,I,T,O,A extends MealyMachine<S,I,T,O> & InputAlphabetHolder<I>> CompactMealy<I,O> minimizeMealy(A mealy)

Minimizes the given Mealy machine. The result is returned in the form of a CompactMealy, using the alphabet obtained via mealy.getInputAlphabet(). Pruning (see above) is performed after computing state equivalences.

Parameters:

mealy - the Mealy machine to minimize

Returns:

a minimized version of the specified Mealy machine

minimizeMealy

public static <S,I,T,O,A extends MealyMachine<S,I,T,O> & InputAlphabetHolder<I>> CompactMealy<I,O> minimizeMealy(A mealy,
                                                                                                                 HopcroftMinimization.PruningMode pruningMode)

Minimizes the given Mealy machine. The result is returned in the form of a CompactMealy, using the alphabet obtained via mealy.getInputAlphabet().

Parameters:

mealy - the Mealy machine to minimize

pruningMode - the pruning mode (see above)

Returns:

a minimized version of the specified Mealy machine

minimizeMealy

public static <I,O> CompactMealy<I,O> minimizeMealy(MealyMachine<?,I,?,O> mealy,
                                                    Alphabet<I> alphabet)

Minimizes the given Mealy machine. The result is returned in the form of a CompactMealy, and pruning (see above) is performed after computing state equivalences.

Parameters:

mealy - the Mealy machine to minimize

alphabet - the input alphabet (this will be the input alphabet of the resulting Mealy machine)

Returns:

a minimized version of the specified Mealy machine

minimizeMealy

public static <I,O> CompactMealy<I,O> minimizeMealy(MealyMachine<?,I,?,O> mealy,
                                                    Alphabet<I> alphabet,
                                                    HopcroftMinimization.PruningMode pruningMode)

Minimizes the given Mealy machine. The result is returned in the form of a CompactMealy.

Parameters:

mealy - the Mealy machine to minimize

alphabet - the input alphabet (this will be the input alphabet of the resulting Mealy machine)

pruningMode - the pruning mode (see above)

Returns:

a minimized version of the specified Mealy machine

minimizeMealy

public static <A extends MutableMealyMachine<?,I,?,O>,I,O> A minimizeMealy(MealyMachine<?,I,?,O> mealy,
                                                                           Alphabet<I> alphabet,
                                                                           HopcroftMinimization.PruningMode pruningMode,
                                                                           AutomatonCreator<A,I> creator)

Minimizes the given Mealy machine. The result is returned in the form of a CompactMealy.

Parameters:

mealy - the Mealy machine to minimize

alphabet - the input alphabet (this will be the input alphabet of the resulting Mealy machine)

pruningMode - the pruning mode (see above)

creator - the creator for constructing the automata instance to return

Returns:

a minimized version of the specified Mealy machine

minimizeUniversal

public static <I,T,SP,TP,A extends MutableDeterministic<?,I,?,SP,TP>> A minimizeUniversal(UniversalDeterministicAutomaton<?,I,T,SP,TP> automaton,
                                                                                          Alphabet<I> alphabet,
                                                                                          AutomatonCreator<A,I> creator,
                                                                                          AutomatonInitialPartitioning ap,
                                                                                          HopcroftMinimization.PruningMode pruningMode)

Minimizes the given automaton depending on the given partitioning function.

Parameters:

automaton - the automaton to minimize

alphabet - the input alphabet (this will be the input alphabet of the resulting Mealy machine)

creator - the creator for constructing the automata instance to return

ap - the initial partitioning function, determining how states will be distinguished

pruningMode - the pruning mode (see above)

Returns:

the minimized automaton, initially constructed from the given creator.

See Also:

AutomatonInitialPartitioning