Package net.automatalib.util.automaton

Class Automata

java.lang.Object

net.automatalib.util.automaton.Automata

public final class Automata
extends Object

Method Summary

Modifier and Type	Method	Description
static <S,I> Iterable<TS.TransRef<S,I,?>>	allDefinedInputs(Automaton<S,I,?> automaton, Iterable<? extends I> inputs)
static <S,I> Iterator<TS.TransRef<S,I,?>>	allDefinedInputsIterator(Automaton<S,I,?> automaton, Iterable<? extends I> inputs)
static <S,I> Iterable<TS.TransRef<S,I,?>>	allUndefinedInputs(Automaton<S,I,?> automaton, Iterable<? extends I> inputs)
static <S,I> Iterator<TS.TransRef<S,I,?>>	allUndefinedInputsIterator(Automaton<S,I,?> automaton, Iterable<? extends I> inputs)
static <S,I,T> Graph<S,TransitionEdge<I,T>>	asGraph(Automaton<S,I,T> automaton, Collection<? extends I> inputs)
static <I> List<Word<I>>	characterizingSet(UniversalDeterministicAutomaton<?,I,?,?,?> automaton, Collection<? extends I> inputs)	Computes a characterizing set, and returns it as a List.
static <I> void	characterizingSet(UniversalDeterministicAutomaton<?,I,?,?,?> automaton, Collection<? extends I> inputs, Collection<? super Word<I>> result)	Computes a characterizing set for the given automaton.
static <I> @Nullable Word<I>	findSeparatingWord(UniversalDeterministicAutomaton<?,I,?,?,?> reference, UniversalDeterministicAutomaton<?,I,?,?,?> other, Collection<? extends I> inputs)	Finds a separating word for two automata.
static <S,I> @Nullable Word<I>	findSeparatingWord(UniversalDeterministicAutomaton<S,I,?,?,?> automaton, S state1, S state2, Collection<? extends I> inputs)	Finds a separating word for two states in an automaton.
static <I> @Nullable Word<I>	findShortestSeparatingWord(UniversalDeterministicAutomaton<?,I,?,?,?> reference, UniversalDeterministicAutomaton<?,I,?,?,?> other, Collection<? extends I> inputs)	Finds a shortest separating word for two automata.
static <I> boolean	hasUndefinedInput(Automaton<?,I,?> automaton, Iterable<? extends I> inputs)
static <I> boolean	incrementalCharacterizingSet(UniversalDeterministicAutomaton<?,I,?,?,?> automaton, Collection<? extends I> inputs, Collection<? extends Word<I>> oldSuffixes, Collection<? super Word<I>> newSuffixes)
static <S,I,T,SP,TP,A extends MutableDeterministic<S,I,T,SP,TP>> A	invasiveMinimize(A automaton, Collection<? extends I> inputs)
static <S,I,T,SP,TP,SO,TO,A extends MutableDeterministic<SO,? super I,TO,? super SP,? super TP>> A	minimize(UniversalDeterministicAutomaton<S,I,T,SP,TP> automaton, Collection<? extends I> inputs, A output)
static <S,I> List<Word<I>>	stateCharacterizingSet(UniversalDeterministicAutomaton<S,I,?,?,?> automaton, Collection<? extends I> inputs, S state)	Computes a characterizing set for a single state, and returns it as a List.
static <S,I> void	stateCharacterizingSet(UniversalDeterministicAutomaton<S,I,?,?,?> automaton, Collection<? extends I> inputs, S state, Collection<? super Word<I>> result)	Computes a characterizing set for a single state.
static <I> List<Word<I>>	stateCover(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs)	Convenient method for computing a state cover.
static <I> List<Word<I>>	structuralCover(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs)	Convenient method for computing a structural cover.
static <I> boolean	testEquivalence(UniversalDeterministicAutomaton<?,I,?,?,?> reference, UniversalDeterministicAutomaton<?,I,?,?,?> other, Collection<? extends I> inputs)	Tests whether two automata are equivalent, i.e. whether there exists a separating word for the two given automata.
static <I> List<Word<I>>	transitionCover(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs)	Convenient method for computing a state cover.

Methods inherited from class java.lang.Object

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

Method Detail

asGraph

public static <S,I,T> Graph<S,TransitionEdge<I,T>> asGraph(Automaton<S,I,T> automaton,
                                                                                   Collection<? extends I> inputs)

minimize

public static <S,I,T,SP,TP,SO,TO,A extends MutableDeterministic<SO,? super I,TO,? super SP,? super TP>> A minimize(UniversalDeterministicAutomaton<S,I,T,SP,TP> automaton,
                                                                                                                                                                                     Collection<? extends I> inputs,
                                                                                                                                                                                     A output)

invasiveMinimize

public static <S,I,T,SP,TP,A extends MutableDeterministic<S,I,T,SP,TP>> A invasiveMinimize(A automaton,
                                                                                                                                                 Collection<? extends I> inputs)

testEquivalence

public static <I> boolean testEquivalence(UniversalDeterministicAutomaton<?,I,?,?,?> reference,
                                          UniversalDeterministicAutomaton<?,I,?,?,?> other,
                                          Collection<? extends I> inputs)

Tests whether two automata are equivalent, i.e. whether there exists a separating word for the two given automata.

Type Parameters:

I - input symbol type

Parameters:

reference - the one automaton to consider

other - the other automaton to consider

inputs - the input symbols to consider

Returns:

true if the automata are equivalent, false otherwise.

See Also:

findSeparatingWord(UniversalDeterministicAutomaton, UniversalDeterministicAutomaton, Collection)

findSeparatingWord

public static <I> @Nullable Word<I> findSeparatingWord(UniversalDeterministicAutomaton<?,I,?,?,?> reference,
                                                       UniversalDeterministicAutomaton<?,I,?,?,?> other,
                                                       Collection<? extends I> inputs)

Finds a separating word for two automata. A separating word is a word that exposes a difference (differing state or transition properties, or a transition undefined in only one of the automata) between the two automata.

Type Parameters:

I - input symbol type

Parameters:

reference - the one automaton to consider

other - the other automaton to consider

inputs - the input symbols to consider

Returns:

a separating word, or null if no such word could be found.

findSeparatingWord

public static <S,I> @Nullable Word<I> findSeparatingWord(UniversalDeterministicAutomaton<S,I,?,?,?> automaton,
                                                               S state1,
                                                               S state2,
                                                               Collection<? extends I> inputs)

Finds a separating word for two states in an automaton. A separating word is a word that exposes a difference (differing state or transition properties, or a transition undefined in only one of the paths) between the two states.

Type Parameters:

S - state type

I - input symbol type

Parameters:

automaton - the automaton containing the states

state1 - the one state

state2 - the other state

inputs - the input symbols to consider

Returns:

a separating word, or null if no such word could be found

findShortestSeparatingWord

public static <I> @Nullable Word<I> findShortestSeparatingWord(UniversalDeterministicAutomaton<?,I,?,?,?> reference,
                                                               UniversalDeterministicAutomaton<?,I,?,?,?> other,
                                                               Collection<? extends I> inputs)

Finds a shortest separating word for two automata. A separating word is a word that exposes a difference (differing state or transition properties, or a transition undefined in only one of the automata) between the two automata.

Type Parameters:

I - input symbol type

Parameters:

reference - the one automaton to consider

other - the other automaton to consider

inputs - the input symbols to consider

Returns:

a separating word, or null if no such word could be found.

characterizingSet

public static <I> List<Word<I>> characterizingSet(UniversalDeterministicAutomaton<?,I,?,?,?> automaton,
                                                  Collection<? extends I> inputs)

Computes a characterizing set, and returns it as a List.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which to determine the characterizing set

inputs - the input symbols to consider

Returns:

a list containing the characterizing words

See Also:

CharacterizingSets

characterizingSet

public static <I> void characterizingSet(UniversalDeterministicAutomaton<?,I,?,?,?> automaton,
                                         Collection<? extends I> inputs,
                                         Collection<? super Word<I>> result)

Computes a characterizing set for the given automaton.

This is a convenience method acting as a shortcut to CharacterizingSets.findCharacterizingSet(UniversalDeterministicAutomaton, Collection, Collection).

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which to determine the characterizing set

inputs - the input symbols to consider

result - the collection in which to store the characterizing words

See Also:

CharacterizingSets

incrementalCharacterizingSet

public static <I> boolean incrementalCharacterizingSet(UniversalDeterministicAutomaton<?,I,?,?,?> automaton,
                                                       Collection<? extends I> inputs,
                                                       Collection<? extends Word<I>> oldSuffixes,
                                                       Collection<? super Word<I>> newSuffixes)

stateCharacterizingSet

public static <S,I> List<Word<I>> stateCharacterizingSet(UniversalDeterministicAutomaton<S,I,?,?,?> automaton,
                                                               Collection<? extends I> inputs,
                                                               S state)

Computes a characterizing set for a single state, and returns it as a List.

Type Parameters:

S - state type

I - input symbol type

Parameters:

automaton - the automaton containing the state

inputs - the input symbols to consider

state - the state for which to determine a characterizing set

Returns:

a list containing the characterizing words

See Also:

CharacterizingSets

stateCharacterizingSet

public static <S,I> void stateCharacterizingSet(UniversalDeterministicAutomaton<S,I,?,?,?> automaton,
                                                      Collection<? extends I> inputs,
                                                      S state,
                                                      Collection<? super Word<I>> result)

Computes a characterizing set for a single state.

This is a convenience method acting as a shortcut to CharacterizingSets.findCharacterizingSet(UniversalDeterministicAutomaton, Collection, Object, Collection).

Type Parameters:

S - state type

I - input symbol type

Parameters:

automaton - the automaton containing the state

inputs - the input symbols to consider

state - the state for which to determine a characterizing set

result - the collection in which to store the characterizing words

See Also:

CharacterizingSets

stateCover

public static <I> List<Word<I>> stateCover(DeterministicAutomaton<?,I,?> automaton,
                                           Collection<? extends I> inputs)

Convenient method for computing a state cover.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

Returns:

the state cover for the given automaton

See Also:

Covers.stateCover(DeterministicAutomaton, Collection, Collection)

transitionCover

public static <I> List<Word<I>> transitionCover(DeterministicAutomaton<?,I,?> automaton,
                                                Collection<? extends I> inputs)

Convenient method for computing a state cover.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

Returns:

the transition cover for the given automaton

See Also:

Covers.transitionCover(DeterministicAutomaton, Collection, Collection)

structuralCover

public static <I> List<Word<I>> structuralCover(DeterministicAutomaton<?,I,?> automaton,
                                                Collection<? extends I> inputs)

Convenient method for computing a structural cover.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

Returns:

the structural cover for the given automaton

See Also:

Covers.structuralCover(DeterministicAutomaton, Collection, Collection)

allDefinedInputsIterator

public static <S,I> Iterator<TS.TransRef<S,I,?>> allDefinedInputsIterator(Automaton<S,I,?> automaton,
                                                                                            Iterable<? extends I> inputs)

allDefinedInputs

public static <S,I> Iterable<TS.TransRef<S,I,?>> allDefinedInputs(Automaton<S,I,?> automaton,
                                                                                    Iterable<? extends I> inputs)

allUndefinedInputs

public static <S,I> Iterable<TS.TransRef<S,I,?>> allUndefinedInputs(Automaton<S,I,?> automaton,
                                                                                      Iterable<? extends I> inputs)

hasUndefinedInput

public static <I> boolean hasUndefinedInput(Automaton<?,I,?> automaton,
                                            Iterable<? extends I> inputs)

allUndefinedInputsIterator

public static <S,I> Iterator<TS.TransRef<S,I,?>> allUndefinedInputsIterator(Automaton<S,I,?> automaton,
                                                                                              Iterable<? extends I> inputs)