net.automatalib.util.automata.cover

Class Covers

java.lang.Object

net.automatalib.util.automata.cover.Covers

public final class Covers
extends Object

Author:

Malte Isberner, frohme

Method Summary

Modifier and Type	Method and Description
static <I> void	cover(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs, Collection<? super Word<I>> states, Collection<? super Word<I>> transitions) Utility method that allows to compute a state and transition cover simultaneously.
static <I> boolean	incrementalCover(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs, Collection<? extends Word<I>> oldStateCover, Collection<? extends Word<I>> oldTransCover, Collection<? super Word<I>> newStateCover, Collection<? super Word<I>> newTransCover) Utility method that allows to compute an incremental state and transition cover simultaneously.
static <S,I> boolean	incrementalStateCover(DeterministicAutomaton<S,I,?> automaton, Collection<? extends I> inputs, Collection<? extends Word<I>> oldStates, Collection<? super Word<I>> newStates) Computes an incremental state cover for a given automaton, i.e. a cover that only contains the missing sequences for obtaining a complete state cover.
static <I> Iterator<Word<I>>	incrementalStateCoverIterator(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs, Collection<? extends Word<I>> stateCover) Returns an iterator for the remaining sequences of a state cover.
static <I> boolean	incrementalStructuralCover(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs, Collection<? extends Word<I>> oldCover, Collection<? super Word<I>> newCover) Computes an incremental structural cover for a given automaton, i.e. a cover that only contains the missing sequences for obtaining a complete structural cover.
static <I> boolean	incrementalTransitionCover(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs, Collection<? extends Word<I>> oldTransCover, Collection<? super Word<I>> newTransCover) Computes an incremental transition cover for a given automaton, i.e. a cover that only contains the missing sequences for obtaining a complete transition cover.
static <I> Iterator<Word<I>>	incrementalTransitionCoverIterator(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs, Collection<? extends Word<I>> transitionCover) Returns an iterator for the remaining sequences of a transition cover.
static <I> void	stateCover(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs, Collection<? super Word<I>> states) Computes a state cover for a given automaton.
static <I> Iterator<Word<I>>	stateCoverIterator(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs) Returns an iterator for the sequences of a state cover.
static <I> void	structuralCover(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs, Collection<? super Word<I>> cover) Computes a structural cover for a given automaton.
static <I> void	transitionCover(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs, Collection<? super Word<I>> transitions) Computes a transition cover for a given automaton.
static <I> Iterator<Word<I>>	transitionCoverIterator(DeterministicAutomaton<?,I,?> automaton, Collection<? extends I> inputs) Returns an iterator for the sequences of a transition cover.

Methods inherited from class java.lang.Object

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

Method Detail

stateCover

public static <I> void stateCover(DeterministicAutomaton<?,I,?> automaton,
                                  Collection<? extends I> inputs,
                                  Collection<? super Word<I>> states)

Computes a state cover for a given automaton.

A state cover is a set C of input sequences, such that for each state s of an automaton, there exists an input sequence in C that transitions the automaton from its initial state to state s.

Note: if restrictions on the inputs parameter do not allow to reach certain states, the computed cover is not complete.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

states - the collection in which the sequences will be stored

stateCoverIterator

public static <I> Iterator<Word<I>> stateCoverIterator(DeterministicAutomaton<?,I,?> automaton,
                                                       Collection<? extends I> inputs)

Returns an iterator for the sequences of a state cover. Sequences are computed lazily (i.e. as requested by the iterators next method.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

Returns:

an iterator for the input sequences of the cover.

See Also:

stateCover(DeterministicAutomaton, Collection, Collection)

transitionCover

public static <I> void transitionCover(DeterministicAutomaton<?,I,?> automaton,
                                       Collection<? extends I> inputs,
                                       Collection<? super Word<I>> transitions)

Computes a transition cover for a given automaton.

A transition cover is a set C of input sequences, such that for each state s and each input symbol i of an automaton, there exists an input sequence in C that starts from the initial state of the automaton and ends with the transition that applies i to state s.

Note: if restrictions on the inputs parameter do not allow to reach certain transitions, the computed cover is not complete.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

transitions - the collection in which the sequences will be stored

transitionCoverIterator

public static <I> Iterator<Word<I>> transitionCoverIterator(DeterministicAutomaton<?,I,?> automaton,
                                                            Collection<? extends I> inputs)

Returns an iterator for the sequences of a transition cover. Sequences are computed lazily (i.e. as requested by the iterators next method.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

Returns:

an iterator for the input sequences of the cover.

See Also:

transitionCover(DeterministicAutomaton, Collection, Collection)

structuralCover

public static <I> void structuralCover(DeterministicAutomaton<?,I,?> automaton,
                                       Collection<? extends I> inputs,
                                       Collection<? super Word<I>> cover)

Computes a structural cover for a given automaton.

A structural cover is the union of a state cover and a transition cover

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

cover - the collection in which the sequences will be stored

See Also:

stateCover(DeterministicAutomaton, Collection, Collection), transitionCover(DeterministicAutomaton, Collection, Collection)

cover

public static <I> void cover(DeterministicAutomaton<?,I,?> automaton,
                             Collection<? extends I> inputs,
                             Collection<? super Word<I>> states,
                             Collection<? super Word<I>> transitions)

Utility method that allows to compute a state and transition cover simultaneously.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the covers should be computed

inputs - the set of input symbols allowed in the cover sequences

states - the collection in which the state cover sequences will be stored

transitions - the collection in which the transition cover sequences will be stored

See Also:

stateCover(DeterministicAutomaton, Collection, Collection), transitionCover(DeterministicAutomaton, Collection, Collection)

incrementalStateCover

public static <S,I> boolean incrementalStateCover(DeterministicAutomaton<S,I,?> automaton,
                                                  Collection<? extends I> inputs,
                                                  Collection<? extends Word<I>> oldStates,
                                                  Collection<? super Word<I>> newStates)

Computes an incremental state cover for a given automaton, i.e. a cover that only contains the missing sequences for obtaining a complete state cover.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

oldStates - the collection containing the already existing sequences of the state cover

newStates - the collection in which the missing sequences will be stored

Returns:

true if new sequences have been added to the state cover, false otherwise.

See Also:

stateCover(DeterministicAutomaton, Collection, Collection)

incrementalStateCoverIterator

public static <I> Iterator<Word<I>> incrementalStateCoverIterator(DeterministicAutomaton<?,I,?> automaton,
                                                                  Collection<? extends I> inputs,
                                                                  Collection<? extends Word<I>> stateCover)

Returns an iterator for the remaining sequences of a state cover. Sequences are computed lazily (i.e. as requested by the iterators next method.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

stateCover - the collection containing the already existing sequences of the state cover

Returns:

an iterator for the remaining input sequences of the cover.

See Also:

incrementalStateCover(DeterministicAutomaton, Collection, Collection, Collection)

incrementalTransitionCover

public static <I> boolean incrementalTransitionCover(DeterministicAutomaton<?,I,?> automaton,
                                                     Collection<? extends I> inputs,
                                                     Collection<? extends Word<I>> oldTransCover,
                                                     Collection<? super Word<I>> newTransCover)

Computes an incremental transition cover for a given automaton, i.e. a cover that only contains the missing sequences for obtaining a complete transition cover.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

oldTransCover - the collection containing the already existing sequences of the transition cover

newTransCover - the collection in which the missing sequences will be stored

Returns:

true if new sequences have been added to the state cover, false otherwise.

See Also:

transitionCover(DeterministicAutomaton, Collection, Collection)

incrementalTransitionCoverIterator

public static <I> Iterator<Word<I>> incrementalTransitionCoverIterator(DeterministicAutomaton<?,I,?> automaton,
                                                                       Collection<? extends I> inputs,
                                                                       Collection<? extends Word<I>> transitionCover)

Returns an iterator for the remaining sequences of a transition cover. Sequences are computed lazily (i.e. as requested by the iterators next method.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

transitionCover - the collection containing the already existing sequences of the transition cover

Returns:

an iterator for the remaining input sequences of the cover.

See Also:

incrementalStateCover(DeterministicAutomaton, Collection, Collection, Collection)

incrementalStructuralCover

public static <I> boolean incrementalStructuralCover(DeterministicAutomaton<?,I,?> automaton,
                                                     Collection<? extends I> inputs,
                                                     Collection<? extends Word<I>> oldCover,
                                                     Collection<? super Word<I>> newCover)

Computes an incremental structural cover for a given automaton, i.e. a cover that only contains the missing sequences for obtaining a complete structural cover.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the cover should be computed

inputs - the set of input symbols allowed in the cover sequences

oldCover - the collection containing the already existing sequences of the structural cover

newCover - the collection in which the missing sequences will be stored

Returns:

true if new sequences have been added to the structural cover, false otherwise.

See Also:

structuralCover(DeterministicAutomaton, Collection, Collection)

incrementalCover

public static <I> boolean incrementalCover(DeterministicAutomaton<?,I,?> automaton,
                                           Collection<? extends I> inputs,
                                           Collection<? extends Word<I>> oldStateCover,
                                           Collection<? extends Word<I>> oldTransCover,
                                           Collection<? super Word<I>> newStateCover,
                                           Collection<? super Word<I>> newTransCover)

Utility method that allows to compute an incremental state and transition cover simultaneously.

Type Parameters:

I - input symbol type

Parameters:

automaton - the automaton for which the covers should be computed

inputs - the set of input symbols allowed in the cover sequences

oldStateCover - the collection containing the already existing sequences of the state cover

oldTransCover - the collection containing the already existing sequences of the transition cover

newStateCover - the collection in which the missing state cover sequences will be stored

newTransCover - the collection in which the missing transition cover sequences will be stored

Returns:

true if new sequences have been added to the structural cover, false otherwise.

See Also:

incrementalStateCover(DeterministicAutomaton, Collection, Collection, Collection), incrementalStateCover(DeterministicAutomaton, Collection, Collection, Collection)