Package de.learnlib.algorithm.ttt.base

Class AbstractTTTLearner<A,I,D>

java.lang.Object

de.learnlib.algorithm.ttt.base.AbstractTTTLearner<A,I,D>

Type Parameters:

I - input symbol type

All Implemented Interfaces:

LearningAlgorithm<A,I,D>, Resumable<TTTLearnerState<I,D>>, SupportsGrowingAlphabet<I>

Direct Known Subclasses:

TTTLearnerDFA, TTTLearnerMealy, TTTLearnerMoore

public abstract class AbstractTTTLearner<A,I,D>
extends Object
implements LearningAlgorithm<A,I,D>, SupportsGrowingAlphabet<I>, Resumable<TTTLearnerState<I,D>>

The TTT learning algorithm for DFA.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	AbstractTTTLearner.BuilderDefaults
static class	AbstractTTTLearner.Splitter<I,D>	Data structure for representing a splitter.

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 Alphabet<I>	alphabet
protected AcexAnalyzer	analyzer
protected BlockList<I,D>	blockList	The blocks during a split operation.
protected BaseTTTDiscriminationTree<I,D>	dtree
protected AbstractTTTHypothesis<?,I,D,?>	hypothesis
protected IncomingList<I,D>	openTransitions	Open transitions, i.e., transitions that possibly point to a non-leaf node in the discrimination tree.
protected MembershipOracle<I,D>	oracle

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	AbstractTTTLearner(Alphabet<I> alphabet, MembershipOracle<I,D> oracle, AbstractTTTHypothesis<?,I,D,?> hypothesis, BaseTTTDiscriminationTree<I,D> dtree, AcexAnalyzer analyzer)

Method Summary

Modifier and Type	Method	Description
void	addAlphabetSymbol(I symbol)
protected boolean	allNodesFinal()
protected void	closeTransitions()
protected abstract D	computeHypothesisOutput(TTTState<I,D> state, Word<I> suffix)
protected <V> Map<D,V>	createMap()
protected abstract AbstractBaseDTNode<I,D>	createNewNode(AbstractBaseDTNode<I,D> parent, D parentOutput)
protected TTTTransition<I,D>	createTransition(TTTState<I,D> state, I sym)
protected void	declareFinal(AbstractBaseDTNode<I,D> blockRoot)
protected OutInconsPrefixTransformAcex<I,D>	deriveAcex(OutputInconsistency<I,D> outIncons)
protected boolean	finalizeAny()	Chooses a block root, and finalizes the corresponding discriminator.
protected OutputInconsistency<I,D>	findOutputInconsistency()
protected TTTState<I,D>	getAnySuccessor(TTTState<I,D> state, I sym)
protected TTTState<I,D>	getAnySuccessor(TTTState<I,D> state, Iterable<? extends I> suffix)
protected TTTState<I,D>	getAnyTarget(TTTTransition<I,D> trans)	Retrieves the target state of a given transition.
protected TTTState<I,D>	getDeterministicState(TTTState<I,D> start, Word<I> word)
BaseTTTDiscriminationTree<I,D>	getDiscriminationTree()	Returns the discrimination tree.
AbstractTTTHypothesis<?,I,D,?>	getHypothesisDS()
protected Set<TTTState<I,D>>	getNondetSuccessors(Collection<? extends TTTState<I,D>> states, I sym)
protected void	initializeState(TTTState<I,D> state)	Initializes a state.
protected static <I,D> void	link(AbstractBaseDTNode<I,D> dtNode, TTTState<I,D> state)	Establish the connection between a node in the discrimination tree and a state of the hypothesis.
protected TTTState<I,D>	makeTree(TTTTransition<I,D> trans)
protected abstract D	predictSuccOutcome(TTTTransition<I,D> trans, AbstractBaseDTNode<I,D> succSeparator)
protected D	query(AccessSequenceProvider<I> accessSeqProvider, Word<I> suffix)	Performs a membership query, using an access sequence as its prefix.
protected D	query(Word<I> prefix, Word<I> suffix)	Performs a membership query.
boolean	refineHypothesis(DefaultQuery<I,D> ceQuery)	Triggers a refinement of the model by providing a counterexample.
protected boolean	refineHypothesisSingle(DefaultQuery<I,D> ceQuery)	Performs a single refinement of the hypothesis, i.e., without repeated counterexample evaluation.
void	resume(TTTLearnerState<I,D> state)	Resume the datastructure from a previously suspended point in time.
protected AbstractDTNode.SplitResult	split(AbstractBaseDTNode<I,D> node, Word<I> discriminator, D oldOutput, D newOutput)
void	startLearning()	Starts the model inference process, creating an initial hypothesis in the provided model object.
protected abstract D	succEffect(D effect)
TTTLearnerState<I,D>	suspend()	Expose the state object.

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.learnlib.algorithm.LearningAlgorithm

getHypothesisModel

Field Detail

alphabet

protected final Alphabet<I> alphabet

oracle

protected final MembershipOracle<I,D> oracle

analyzer

protected final AcexAnalyzer analyzer

openTransitions

protected final IncomingList<I,D> openTransitions

Open transitions, i.e., transitions that possibly point to a non-leaf node in the discrimination tree.

blockList

protected final BlockList<I,D> blockList

The blocks during a split operation. A block is a maximal subtree of the discrimination tree containing temporary discriminators at its root.

hypothesis

protected AbstractTTTHypothesis<?,I,D,?> hypothesis

dtree

protected BaseTTTDiscriminationTree<I,D> dtree

Constructor Detail

AbstractTTTLearner

protected AbstractTTTLearner(Alphabet<I> alphabet,
                             MembershipOracle<I,D> oracle,
                             AbstractTTTHypothesis<?,I,D,?> hypothesis,
                             BaseTTTDiscriminationTree<I,D> dtree,
                             AcexAnalyzer analyzer)

Method Detail

link

protected static <I,D> void link(AbstractBaseDTNode<I,D> dtNode,
                                       TTTState<I,D> state)

Establish the connection between a node in the discrimination tree and a state of the hypothesis.

Parameters:

dtNode - the node in the discrimination tree

state - the state in the hypothesis

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<A,I,D>

refineHypothesis

public boolean refineHypothesis(DefaultQuery<I,D> 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<A,I,D>

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).

initializeState

protected void initializeState(TTTState<I,D> state)

Initializes a state. Creates its outgoing transition objects, and adds them to the "open" list.

Parameters:

state - the state to initialize

createTransition

protected TTTTransition<I,D> createTransition(TTTState<I,D> state,
                                                    I sym)

refineHypothesisSingle

protected boolean refineHypothesisSingle(DefaultQuery<I,D> ceQuery)

Performs a single refinement of the hypothesis, i.e., without repeated counterexample evaluation. The parameter and return value have the same significance as in refineHypothesis(DefaultQuery).

Parameters:

ceQuery - the counterexample (query) to be used for refinement

Returns:

true if the hypothesis was refined, false otherwise

deriveAcex

protected OutInconsPrefixTransformAcex<I,D> deriveAcex(OutputInconsistency<I,D> outIncons)

succEffect

protected abstract D succEffect(D effect)

finalizeAny

protected boolean finalizeAny()

Chooses a block root, and finalizes the corresponding discriminator.

Returns:

true if a splittable block root was found, false otherwise.

getDeterministicState

protected TTTState<I,D> getDeterministicState(TTTState<I,D> start,
                                                    Word<I> word)

getNondetSuccessors

protected Set<TTTState<I,D>> getNondetSuccessors(Collection<? extends TTTState<I,D>> states,
                                                       I sym)

getAnySuccessor

protected TTTState<I,D> getAnySuccessor(TTTState<I,D> state,
                                              I sym)

getAnySuccessor

protected TTTState<I,D> getAnySuccessor(TTTState<I,D> state,
                                              Iterable<? extends I> suffix)

getAnyTarget

protected TTTState<I,D> getAnyTarget(TTTTransition<I,D> trans)

Retrieves the target state of a given transition. This method works for both tree and non-tree transitions. If a non-tree transition points to a non-leaf node, it is updated accordingly before a result is obtained.

Parameters:

trans - the transition

Returns:

the target state of this transition (possibly after it having been updated)

findOutputInconsistency

protected OutputInconsistency<I,D> findOutputInconsistency()

allNodesFinal

protected boolean allNodesFinal()

declareFinal

protected void declareFinal(AbstractBaseDTNode<I,D> blockRoot)

predictSuccOutcome

protected abstract D predictSuccOutcome(TTTTransition<I,D> trans,
                                        AbstractBaseDTNode<I,D> succSeparator)

createMap

protected <V> Map<D,V> createMap()

computeHypothesisOutput

protected abstract D computeHypothesisOutput(TTTState<I,D> state,
                                             Word<I> suffix)

getHypothesisDS

public AbstractTTTHypothesis<?,I,D,?> getHypothesisDS()

closeTransitions

protected void closeTransitions()

makeTree

protected TTTState<I,D> makeTree(TTTTransition<I,D> trans)

query

protected D query(Word<I> prefix,
                  Word<I> suffix)

Performs a membership query.

Parameters:

prefix - the prefix part of the query

suffix - the suffix part of the query

Returns:

the output

query

protected D query(AccessSequenceProvider<I> accessSeqProvider,
                  Word<I> suffix)

Performs a membership query, using an access sequence as its prefix.

Parameters:

accessSeqProvider - the object from which to obtain the access sequence

suffix - the suffix part of the query

Returns:

the output

getDiscriminationTree

public BaseTTTDiscriminationTree<I,D> getDiscriminationTree()

Returns the discrimination tree.

Returns:

the discrimination tree

split

protected final AbstractDTNode.SplitResult split(AbstractBaseDTNode<I,D> node,
                                                 Word<I> discriminator,
                                                 D oldOutput,
                                                 D newOutput)

addAlphabetSymbol

public void addAlphabetSymbol(I symbol)

Specified by:

addAlphabetSymbol in interface SupportsGrowingAlphabet<A>

createNewNode

protected abstract AbstractBaseDTNode<I,D> createNewNode(AbstractBaseDTNode<I,D> parent,
                                                               D parentOutput)

suspend

public TTTLearnerState<I,D> suspend()

Description copied from interface: Resumable

Expose the state object.

Specified by:

suspend in interface Resumable<A>

Returns:

The state.

resume

public void resume(TTTLearnerState<I,D> state)

Description copied from interface: Resumable

Resume the datastructure from a previously suspended point in time.

Specified by:

resume in interface Resumable<A>

Parameters:

state - The learner state.