Class BacktrackingSearch
- java.lang.Object
-
- net.automatalib.util.automaton.ads.BacktrackingSearch
-
public final class BacktrackingSearch extends Object
A class containing methods for computing adaptive distinguishing sequences (for arbitrary sets of states) by means of a backtracking approach.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
BacktrackingSearch.CostAggregator
Utility enum, that allows to specify the optimization criterion when performing and optimal ADS search.
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static <S,I,O>
Optional<ADSNode<S,I,O>>compute(MealyMachine<S,I,?,O> automaton, Alphabet<I> input, Set<S> states)
Computes an ADS by constructing (growing) splitting words for the current set of states and recursively computing sub-ADSs for the induced partitions.static <S,I,O>
Optional<ADSNode<S,I,O>>computeOptimal(MealyMachine<S,I,?,O> automaton, Alphabet<I> input, Set<S> states, BacktrackingSearch.CostAggregator costAggregator)
Computes an ADS by iterating over the successor tree in a breadth-first manner, yielding an optimal (dependent on the passed optimization function) ADS.
-
-
-
Method Detail
-
compute
public static <S,I,O> Optional<ADSNode<S,I,O>> compute(MealyMachine<S,I,?,O> automaton, Alphabet<I> input, Set<S> states)
Computes an ADS by constructing (growing) splitting words for the current set of states and recursively computing sub-ADSs for the induced partitions. May yield non-optimal ADSs.- Type Parameters:
S
- (hypothesis) state typeI
- input alphabet typeO
- output alphabet type- Parameters:
automaton
- The automaton for which an ADS should be computedinput
- the input alphabet of the automatonstates
- the set of states which should be distinguished by the computed ADS- Returns:
Optional.empty()
if there exists no ADS that distinguishes the given states, a valid ADS otherwise.
-
computeOptimal
public static <S,I,O> Optional<ADSNode<S,I,O>> computeOptimal(MealyMachine<S,I,?,O> automaton, Alphabet<I> input, Set<S> states, BacktrackingSearch.CostAggregator costAggregator)
Computes an ADS by iterating over the successor tree in a breadth-first manner, yielding an optimal (dependent on the passed optimization function) ADS.- Type Parameters:
S
- (hypothesis) state typeI
- input alphabet typeO
- output alphabet type- Parameters:
automaton
- The automaton for which an ADS should be computedinput
- the input alphabet of the automatonstates
- the set of states which should be distinguished by the computed ADScostAggregator
- the optimization function by which solutions should be pruned- Returns:
Optional.empty()
if there exists no ADS that distinguishes the given states, a valid ADS otherwise.
-
-