net.automatalib.util.automata

Class Automata

java.lang.Object

net.automatalib.util.ts.TS

net.automatalib.util.automata.Automata

public class Automata
extends TS

Nested Class Summary

Nested classes/interfaces inherited from class net.automatalib.util.ts.TS

TS.TransRef<S,I,T>

Constructor Summary

Constructors

Constructor and Description
Automata()

Method Summary

Modifier and Type	Method and 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 <S,I,T,SP,TP> UniversalGraph<S,TransitionEdge<I,T>,SP,TransitionEdge.Property<I,TP>>	asUniversalGraph(UniversalAutomaton<S,I,T,SP,TP> 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(OneSEVPA<?,I> sevpa1, OneSEVPA<?,I> sevpa2, VPDAlphabet<I> inputs)
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)
static <S,I> @Nullable TS.TransRef<S,I,?>	findUndefinedInput(Automaton<S,I,?> automaton, Iterable<? extends I> inputs)
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(OneSEVPA<?,I> sevpa1, OneSEVPA<?,I> sevpa2, VPDAlphabet<I> inputs)
static <I> boolean	testEquivalence(UniversalDeterministicAutomaton<?,I,?,?,?> reference, UniversalDeterministicAutomaton<?,I,?,?,?> other, Collection<? extends I> inputs)
static <I> List<Word<I>>	transitionCover(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs) Convenient method for computing a state cover.

Methods inherited from class net.automatalib.util.ts.TS

allDefinedInputs, allDefinedInputsIterator, allUndefinedTransitions, allUndefinedTransitionsIterator, bfsOrder, bfsOrderIterator, definedInputs, definedInputsIterator, stateProperties, transitionProperties, undefinedInputs, undefinedInputsIterator

Methods inherited from class java.lang.Object

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

Constructor Detail

Automata

public Automata()

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)

asUniversalGraph

public static <S,I,T,SP,TP> UniversalGraph<S,TransitionEdge<I,T>,SP,TransitionEdge.Property<I,TP>> asUniversalGraph(UniversalAutomaton<S,I,T,SP,TP> automaton,
                                                                                                                    Collection<? extends I> inputs)

invasiveMinimize

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

findShortestSeparatingWord

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

testEquivalence

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

testEquivalence

public static <I> boolean testEquivalence(OneSEVPA<?,I> sevpa1,
                                          OneSEVPA<?,I> sevpa2,
                                          VPDAlphabet<I> inputs)

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

findSeparatingWord

public static <I> @Nullable Word<I> findSeparatingWord(OneSEVPA<?,I> sevpa1,
                                                       OneSEVPA<?,I> sevpa2,
                                                       VPDAlphabet<I> inputs)

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)

findUndefinedInput

public static <S,I> @Nullable TS.TransRef<S,I,?> findUndefinedInput(Automaton<S,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)