net.automatalib.util.automata.ads

Class LeeYannakakis

java.lang.Object

net.automatalib.util.automata.ads.LeeYannakakis

public final class LeeYannakakis
extends Object

Algorithm of Lee and Yannakakis for computing adaptive distinguishing sequences (of length at most n^2) in O(n^2) time (where n denotes the number of states of the automaton).

See: D. Lee and M. Yannakakis - "Testing Finite-State Machines: State Identification and Verification", IEEE Transactions on Computers 43.3 (1994)

Author:

frohme

Method Summary

Modifier and Type	Method and Description
static <S,I,O> LYResult<S,I,O>	compute(MealyMachine<S,I,?,O> automaton, Alphabet<I> input) Computes an ADS using the algorithm of Lee and Yannakakis.

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> LYResult<S,I,O> compute(MealyMachine<S,I,?,O> automaton,
                                              Alphabet<I> input)

Computes an ADS using the algorithm of Lee and Yannakakis.

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

Returns:

A LYResult containing an adaptive distinguishing sequence (if existent) and a possible set of indistinguishable states.