Package net.automatalib.util.automaton
Class Automata
- java.lang.Object
-
- net.automatalib.util.automaton.Automata
-
public final class Automata extends Object
-
-
Method Summary
All Methods Static Methods Concrete Methods 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 aList
.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>>
AinvasiveMinimize(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>>
Aminimize(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 aList
.static <S,I>
voidstateCharacterizingSet(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 aseparating 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.
-
-
-
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 aseparating word
for the two given automata.- Type Parameters:
I
- input symbol type- Parameters:
reference
- the one automaton to considerother
- the other automaton to considerinputs
- 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 considerother
- the other automaton to considerinputs
- 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 typeI
- input symbol type- Parameters:
automaton
- the automaton containing the statesstate1
- the one statestate2
- the other stateinputs
- 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 considerother
- the other automaton to considerinputs
- 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 aList
.- Type Parameters:
I
- input symbol type- Parameters:
automaton
- the automaton for which to determine the characterizing setinputs
- 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 setinputs
- the input symbols to considerresult
- 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 aList
.- Type Parameters:
S
- state typeI
- input symbol type- Parameters:
automaton
- the automaton containing the stateinputs
- the input symbols to considerstate
- 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 typeI
- input symbol type- Parameters:
automaton
- the automaton containing the stateinputs
- the input symbols to considerstate
- the state for which to determine a characterizing setresult
- 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 computedinputs
- 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 computedinputs
- 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 computedinputs
- 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)
-
-