net.automatalib.util.automata.equivalence

Class CharacterizingSets

java.lang.Object

net.automatalib.util.automata.equivalence.CharacterizingSets

@ParametersAreNonnullByDefault
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.

Author:

Malte Isberner

Method Summary

Modifier and Type	Method and Description
static <S,I,T> Iterator<Word<I>>	characterizingSetIterator(UniversalDeterministicAutomaton<S,I,T,?,?> automaton, Collection<? extends I> inputs)
static <S,I,T> void	findCharacterizingSet(UniversalDeterministicAutomaton<S,I,T,?,?> automaton, Collection<? extends I> inputs, Collection<? super Word<I>> result) Computes a characterizing set for the given automaton.
static <S,I,T> void	findCharacterizingSet(UniversalDeterministicAutomaton<S,I,T,?,?> 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,T> boolean	findIncrementalCharacterizingSet(UniversalDeterministicAutomaton<S,I,T,?,?> automaton, Collection<? extends I> inputs, Collection<? extends Word<I>> oldSuffixes, Collection<? super Word<I>> newSuffixes)
static <S,I,T> Iterator<Word<I>>	incrementalCharacterizingSetIterator(UniversalDeterministicAutomaton<S,I,T,?,?> 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 <S,I,T> void findCharacterizingSet(UniversalDeterministicAutomaton<S,I,T,?,?> 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,T> void findCharacterizingSet(UniversalDeterministicAutomaton<S,I,T,?,?> 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 <S,I,T> Iterator<Word<I>> characterizingSetIterator(UniversalDeterministicAutomaton<S,I,T,?,?> automaton,
                                                                  Collection<? extends I> inputs)

findIncrementalCharacterizingSet

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

incrementalCharacterizingSetIterator

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