Package net.automatalib.util.automaton.ads

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

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.

Methods inherited from class java.lang.Object

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

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 type

I - input alphabet type

O - output alphabet type

Parameters:

automaton - The automaton for which an ADS should be computed

input - the input alphabet of the automaton

states - 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 type

I - input alphabet type

O - output alphabet type

Parameters:

automaton - The automaton for which an ADS should be computed

input - the input alphabet of the automaton

states - the set of states which should be distinguished by the computed ADS

costAggregator - 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.