Package de.learnlib.algorithm.kv.dfa

Class KearnsVaziraniDFA<I>

java.lang.Object

de.learnlib.algorithm.kv.dfa.KearnsVaziraniDFA<I>

Type Parameters:

I - input symbol type

All Implemented Interfaces:

LearningAlgorithm<DFA<?,I>,I,Boolean>, LearningAlgorithm.DFALearner<I>, Resumable<KearnsVaziraniDFAState<I>>, SupportsGrowingAlphabet<I>

Direct Known Subclasses:

KearnsVaziraniAdapterDFA

public class KearnsVaziraniDFA<I>
extends Object
implements LearningAlgorithm.DFALearner<I>, SupportsGrowingAlphabet<I>, Resumable<KearnsVaziraniDFAState<I>>

The Kearns/Vazirani algorithm for learning DFA, as described in the book "An Introduction to Computational Learning Theory" by Michael Kearns and Umesh Vazirani.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	KearnsVaziraniDFA.KVAbstractCounterexample

Nested classes/interfaces inherited from interface de.learnlib.algorithm.LearningAlgorithm

LearningAlgorithm.DFALearner<I>, LearningAlgorithm.MealyLearner<I,O>, LearningAlgorithm.MooreLearner<I,O>, LearningAlgorithm.NFALearner<I>

Field Summary

Fields

Modifier and Type	Field	Description
protected List<StateInfo<I,Boolean>>	stateInfos

Constructor Summary

Constructors

Constructor	Description
KearnsVaziraniDFA(Alphabet<I> alphabet, MembershipOracle<I,Boolean> oracle, boolean repeatedCounterexampleEvaluation, AcexAnalyzer counterexampleAnalyzer)	Constructor.

Method Summary

Modifier and Type	Method	Description
void	addAlphabetSymbol(I symbol)
BinaryDTree<I,StateInfo<I,Boolean>>	getDiscriminationTree()
DFA<?,I>	getHypothesisModel()	Returns the current hypothesis model.
boolean	refineHypothesis(DefaultQuery<I,Boolean> ceQuery)	Triggers a refinement of the model by providing a counterexample.
void	resume(KearnsVaziraniDFAState<I> state)	Resume the datastructure from a previously suspended point in time.
void	startLearning()	Starts the model inference process, creating an initial hypothesis in the provided model object.
KearnsVaziraniDFAState<I>	suspend()	Expose the state object.

Methods inherited from class java.lang.Object

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

Field Detail

stateInfos

protected List<StateInfo<I,Boolean>> stateInfos

Constructor Detail

KearnsVaziraniDFA

public KearnsVaziraniDFA(Alphabet<I> alphabet,
                         MembershipOracle<I,Boolean> oracle,
                         boolean repeatedCounterexampleEvaluation,
                         AcexAnalyzer counterexampleAnalyzer)

Constructor.

Parameters:

alphabet - the learning alphabet

oracle - the membership oracle

Method Detail

startLearning

public void startLearning()

Description copied from interface: LearningAlgorithm

Starts the model inference process, creating an initial hypothesis in the provided model object. Please note that it should be illegal to invoke this method twice.

Specified by:

startLearning in interface LearningAlgorithm<DFA<?,I>,I,Boolean>

refineHypothesis

public boolean refineHypothesis(DefaultQuery<I,Boolean> ceQuery)

Description copied from interface: LearningAlgorithm

Triggers a refinement of the model by providing a counterexample. A counterexample is a query which exposes different behavior of the real SUL compared to the hypothesis. Please note that invoking this method before an initial invocation of LearningAlgorithm.startLearning() should be illegal.

Specified by:

refineHypothesis in interface LearningAlgorithm<DFA<?,I>,I,Boolean>

Parameters:

ceQuery - the query which exposes diverging behavior, as posed to the real SUL (i.e. with the SULs output).

Returns:

true if the counterexample triggered a refinement of the hypothesis, false otherwise (i.e., it was no counterexample).

getHypothesisModel

public DFA<?,I> getHypothesisModel()

Description copied from interface: LearningAlgorithm

Returns the current hypothesis model.

N.B.: By the contract of this interface, the model returned by this method may not be modified (i.e., M generally should refer to an immutable interface), and its validity is retained only until the next invocation of LearningAlgorithm.refineHypothesis(DefaultQuery). If older hypotheses have to be maintained, a copy of the returned model must be made.

Please note that it should be illegal to invoke this method before an initial invocation of LearningAlgorithm.startLearning().

Specified by:

getHypothesisModel in interface LearningAlgorithm<DFA<?,I>,I,Boolean>

Returns:

the current hypothesis model.

getDiscriminationTree

public BinaryDTree<I,StateInfo<I,Boolean>> getDiscriminationTree()

addAlphabetSymbol

public void addAlphabetSymbol(I symbol)

Specified by:

addAlphabetSymbol in interface SupportsGrowingAlphabet<I>

suspend

public KearnsVaziraniDFAState<I> suspend()

Description copied from interface: Resumable

Expose the state object.

Specified by:

suspend in interface Resumable<I>

Returns:

The state.

resume

public void resume(KearnsVaziraniDFAState<I> state)

Description copied from interface: Resumable

Resume the datastructure from a previously suspended point in time.

Specified by:

resume in interface Resumable<I>

Parameters:

state - The learner state.