Module net.automatalib.util

Package net.automatalib.util.automaton.equivalence

Class NearLinearEquivalenceTest

java.lang.Object

net.automatalib.util.automaton.equivalence.NearLinearEquivalenceTest

public final class NearLinearEquivalenceTest
extends Object

Implements Hopcroft and Karp's equivalence test, as described in A linear algorithm for testing equivalence of finite automata.

Method Summary

Modifier and Type	Method	Description
static <I> @Nullable Word<I>	findSeparatingWord(UniversalDeterministicAutomaton<?,I,?,?,?> target, UniversalDeterministicAutomaton<?,I,?,?,?> other, Collection<? extends I> inputs)
static <I> @Nullable Word<I>	findSeparatingWord(UniversalDeterministicAutomaton<?,I,?,?,?> target, UniversalDeterministicAutomaton<?,I,?,?,?> other, Alphabet<I> inputs)
static <S,I> @Nullable Word<I>	findSeparatingWord(UniversalDeterministicAutomaton<S,I,?,?,?> target, S init1, S init2, Collection<? extends I> inputs)
static <S,I,T> @Nullable Word<I>	findSeparatingWord(UniversalDeterministicAutomaton<S,I,T,?,?> target, S init1, S init2, Collection<? extends I> inputs, boolean ignoreUndefinedTransitions)	Find a separating word for two states in a given automaton.
static <S,S2,I,T,T2,SP,SP2,TP,TP2> @Nullable Word<I>	findSeparatingWord(UniversalDeterministicAutomaton<S,I,T,SP,TP> target, UniversalDeterministicAutomaton<S2,I,T2,SP2,TP2> other, Collection<? extends I> inputs, boolean ignoreUndefinedTransitions)
static <S,S2,I,T,T2,SP,SP2,TP,TP2> @Nullable Word<I>	findSeparatingWord(UniversalDeterministicAutomaton<S,I,T,SP,TP> target, UniversalDeterministicAutomaton<S2,I,T2,SP2,TP2> other, Alphabet<I> inputs, boolean ignoreUndefinedTransitions)

Methods inherited from class java.lang.Object

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

Method Detail

findSeparatingWord

public static <S,I> @Nullable Word<I> findSeparatingWord(UniversalDeterministicAutomaton<S,I,?,?,?> target,
                                                               S init1,
                                                               S init2,
                                                               Collection<? extends I> inputs)

findSeparatingWord

public static <S,I,T> @Nullable Word<I> findSeparatingWord(UniversalDeterministicAutomaton<S,I,T,?,?> target,
                                                                       S init1,
                                                                       S init2,
                                                                       Collection<? extends I> inputs,
                                                                       boolean ignoreUndefinedTransitions)

Find a separating word for two states in a given automaton.

Type Parameters:

S - automaton state type

I - input alphabet type

T - automaton transition type

Parameters:

target - the automaton

init1 - the first state

init2 - the second state

inputs - the inputs to consider for a separating word

ignoreUndefinedTransitions - if true, undefined transitions are not considered to distinguish two states, if false an undefined and defined transition are considered to distinguish two states

Returns:

A word separating the two states, null if no such word can be found

findSeparatingWord

public static <I> @Nullable Word<I> findSeparatingWord(UniversalDeterministicAutomaton<?,I,?,?,?> target,
                                                       UniversalDeterministicAutomaton<?,I,?,?,?> other,
                                                       Collection<? extends I> inputs)

findSeparatingWord

public static <S,S2,I,T,T2,SP,SP2,TP,TP2> @Nullable Word<I> findSeparatingWord(UniversalDeterministicAutomaton<S,I,T,SP,TP> target,
                                                                                                                               UniversalDeterministicAutomaton<S2,I,T2,SP2,TP2> other,
                                                                                                                               Collection<? extends I> inputs,
                                                                                                                               boolean ignoreUndefinedTransitions)

findSeparatingWord

public static <I> @Nullable Word<I> findSeparatingWord(UniversalDeterministicAutomaton<?,I,?,?,?> target,
                                                       UniversalDeterministicAutomaton<?,I,?,?,?> other,
                                                       Alphabet<I> inputs)

findSeparatingWord

public static <S,S2,I,T,T2,SP,SP2,TP,TP2> @Nullable Word<I> findSeparatingWord(UniversalDeterministicAutomaton<S,I,T,SP,TP> target,
                                                                                                                               UniversalDeterministicAutomaton<S2,I,T2,SP2,TP2> other,
                                                                                                                               Alphabet<I> inputs,
                                                                                                                               boolean ignoreUndefinedTransitions)