Package net.automatalib.util.automaton.equivalence

Class CharacterizingSets

java.lang.Object

net.automatalib.util.automaton.equivalence.CharacterizingSets

public final class CharacterizingSets
extends Object

Operations for calculating characterizing sets.

A characterizing set for a whole automaton is a set W of words such that for every two states s₁ and s₂, there exists a word w ∈ W such that w exposes a difference between s₁ and s₂ (i.e., either covers a transition with differing property (or not defined in only one case), or reaching a successor state with differing properties), or there exists no such word at all.

A characterizing set for a single state s is a set W of words such that for every state t, there exists a word w ∈ W such that w exposes a difference between s and t, or there exists no such word at all.

Method Summary

Modifier and Type	Method	Description
static <I> Iterator<Word<I>>	characterizingSetIterator(UniversalDeterministicAutomaton<?,I,?,?,?> automaton, Collection<? extends I> inputs)
static <I> void	findCharacterizingSet(UniversalDeterministicAutomaton<?,I,?,?,?> automaton, Collection<? extends I> inputs, Collection<? super Word<I>> result)	Computes a characterizing set for the given automaton.
static <S,I> void	findCharacterizingSet(UniversalDeterministicAutomaton<S,I,?,?,?> automaton, Collection<? extends I> inputs, S state, Collection<? super Word<I>> result)	Computes a characterizing set for a specified state in the given automaton.
static <S,I> boolean	findIncrementalCharacterizingSet(UniversalDeterministicAutomaton<S,I,?,?,?> automaton, Collection<? extends I> inputs, Collection<? extends Word<I>> oldSuffixes, Collection<? super Word<I>> newSuffixes)
static <I> Iterator<Word<I>>	incrementalCharacterizingSetIterator(UniversalDeterministicAutomaton<?,I,?,?,?> automaton, Collection<? extends I> inputs, Collection<? extends Word<I>> oldSuffixes)

Methods inherited from class java.lang.Object

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

Method Detail

findCharacterizingSet

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

Computes a characterizing set for the given automaton.

Parameters:

automaton - the automaton for which to determine the characterizing set.

inputs - the input alphabets to consider

result - the collection in which to store the characterizing words

findCharacterizingSet

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

Computes a characterizing set for a specified state in the given automaton.

Parameters:

automaton - the automaton containing the state

inputs - the input alphabets to consider

state - the state for which to determine the characterizing set

result - the collection in which to store the characterizing words

characterizingSetIterator

public static <I> Iterator<Word<I>> characterizingSetIterator(UniversalDeterministicAutomaton<?,I,?,?,?> automaton,
                                                              Collection<? extends I> inputs)

findIncrementalCharacterizingSet

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

incrementalCharacterizingSetIterator

public static <I> Iterator<Word<I>> incrementalCharacterizingSetIterator(UniversalDeterministicAutomaton<?,I,?,?,?> automaton,
                                                                         Collection<? extends I> inputs,
                                                                         Collection<? extends Word<I>> oldSuffixes)