net.automatalib.util.automata.minimizer.paigetarjan

Class PaigeTarjanMinimization

java.lang.Object

net.automatalib.util.automata.minimizer.paigetarjan.PaigeTarjanMinimization

public final class PaigeTarjanMinimization
extends Object

A utility class that offers short-hand methods for minimizing automata using the partition refinement approach of PaigeTarjan.

This implementation is specifically tailored towards partial automata by allowing to provide a custom sinkClassification, which will be used as the on-demand "successor" of undefined transitions. When extracting information from the PaigeTarjan datastructure via PaigeTarjanExtractors, the original automaton is used to determine the state-transitions from one partition block to another. If the sinkClassification did not match the signature of any existing state, no transition will enter the artificial partition block of the sink. Consequently, this class will always prune unreachable states, because otherwise we might not return a minimal automaton.

For minimizing complete automata, use HopcroftMinimization.

Author:

frohme

See Also:

PaigeTarjan, HopcroftMinimization

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 <I> CompactDFA<I>	minimizeDFA(DFA<?,I> dfa, Alphabet<I> alphabet) Minimizes the given DFA.
static <A extends MutableDFA<?,I>,I> A	minimizeDFA(DFA<?,I> dfa, Alphabet<I> alphabet, 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 <I,O> CompactMealy<I,O>	minimizeMealy(MealyMachine<?,I,?,O> mealy, Alphabet<I> alphabet) Minimizes the given Mealy machine.
static <A extends MutableMealyMachine<?,I,?,O>,I,O> A	minimizeMealy(MealyMachine<?,I,?,O> mealy, Alphabet<I> alphabet, 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, Object sinkClassification) 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().

Parameters:

dfa - the DFA to minimize

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.

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 <A extends MutableDFA<?,I>,I> A minimizeDFA(DFA<?,I> dfa,
                                                          Alphabet<I> alphabet,
                                                          AutomatonCreator<A,I> creator)

Minimizes the given DFA. The result is returned in the form of a MutableDFA, constructed by the given creator.

Parameters:

dfa - the DFA to minimize

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

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().

Parameters:

mealy - the Mealy machine to minimize

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.

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 <A extends MutableMealyMachine<?,I,?,O>,I,O> A minimizeMealy(MealyMachine<?,I,?,O> mealy,
                                                                           Alphabet<I> alphabet,
                                                                           AutomatonCreator<A,I> creator)

Minimizes the given Mealy machine. The result is returned in the form of a MutableMealyMachine, constructed by the given creator.

Parameters:

mealy - the Mealy machine 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

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,
                                                                                          Object sinkClassification)

Minimizes the given automaton depending on the given partitioning function. The sinkClassification is used to describe the signature of the sink state ("successor" of undefined transitions) and may introduce a new, on-thy-fly equivalence class if it doesn't match a signature of any existing state. See the StateSignature class for creating signatures for existing states.

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

sinkClassification - the classification used when an undefined transition is encountered

Returns:

the minimized automaton, initially constructed from the given creator.

See Also:

AutomatonInitialPartitioning, StateSignature