de.learnlib.algorithms.kv.dfa

Class KearnsVaziraniDFA<I>

java.lang.Object

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

Type Parameters:

I - input symbol type

All Implemented Interfaces:

ResumableLearner<de.learnlib.algorithms.kv.dfa.KearnsVaziraniDFAState<I>>, SupportsGrowingAlphabet<I>, LearningAlgorithm<net.automatalib.automata.fsa.DFA<?,I>,I,Boolean>, LearningAlgorithm.DFALearner<I>

public class KearnsVaziraniDFA<I>
extends Object
implements LearningAlgorithm.DFALearner<I>, SupportsGrowingAlphabet<I>, ResumableLearner<de.learnlib.algorithms.kv.dfa.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.

Author:

Malte Isberner

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	KearnsVaziraniDFA.KVAbstractCounterexample

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

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

Field Summary

Fields

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

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
void	addAlphabetSymbol(I symbol)
net.automatalib.automata.fsa.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(de.learnlib.algorithms.kv.dfa.KearnsVaziraniDFAState<I> state) Does not get the learner to continue learning.
void	startLearning() Starts the model inference process, creating an initial hypothesis in the provided model object.
de.learnlib.algorithms.kv.dfa.KearnsVaziraniDFAState<I>	suspend() Expose the serializable learner state object.

Methods inherited from class java.lang.Object

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

Field Detail

discriminationTree

protected BinaryDTree<I,StateInfo<I,Boolean>> discriminationTree

stateInfos

protected List<StateInfo<I,Boolean>> stateInfos

Constructor Detail

KearnsVaziraniDFA

public KearnsVaziraniDFA(net.automatalib.words.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<net.automatalib.automata.fsa.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<net.automatalib.automata.fsa.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 net.automatalib.automata.fsa.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<net.automatalib.automata.fsa.DFA<?,I>,I,Boolean>

Returns:

the current hypothesis model.

addAlphabetSymbol

public void addAlphabetSymbol(I symbol)

Specified by:

addAlphabetSymbol in interface SupportsGrowingAlphabet<I>

suspend

public de.learnlib.algorithms.kv.dfa.KearnsVaziraniDFAState<I> suspend()

Description copied from interface: ResumableLearner

Expose the serializable learner state object.

Does not stop a running learning process. Since most data structures that are used during learning are mutable, use this method inside of a learning loop with care.

Specified by:

suspend in interface ResumableLearner<de.learnlib.algorithms.kv.dfa.KearnsVaziraniDFAState<I>>

Returns:

The learner state.

resume

public void resume(de.learnlib.algorithms.kv.dfa.KearnsVaziraniDFAState<I> state)

Description copied from interface: ResumableLearner

Does not get the learner to continue learning. Instead, the learner updates its internal state according to the given state object.

Specified by:

resume in interface ResumableLearner<de.learnlib.algorithms.kv.dfa.KearnsVaziraniDFAState<I>>

Parameters:

state - The learner state.