Module de.learnlib.algorithm.lstar

Package de.learnlib.algorithm.lstar

Class AbstractAutomatonLStar<A,I,D,S,T,SP,TP,AI extends net.automatalib.automaton.MutableDeterministic<S,I,T,SP,TP> & net.automatalib.alphabet.SupportsGrowingAlphabet<I>>

java.lang.Object

de.learnlib.algorithm.lstar.AbstractLStar<A,I,D>

de.learnlib.algorithm.lstar.AbstractAutomatonLStar<A,I,D,S,T,SP,TP,AI>

Type Parameters:

A - automaton type, must be a subclass of MutableDeterministic

I - input symbol type

D - output domain type

SP - state property type

TP - transition property type

All Implemented Interfaces:

GlobalSuffixLearner<A,I,D>, LearningAlgorithm<A,I,D>, ObservationTableFeature<I,D>, OTLearner<A,I,D>, Resumable<AutomatonLStarState<I,D,AI,S>>, net.automatalib.alphabet.SupportsGrowingAlphabet<I>

Direct Known Subclasses:

AbstractExtensibleAutomatonLStar

public abstract class AbstractAutomatonLStar<A,I,D,S,T,SP,TP,AI extends net.automatalib.automaton.MutableDeterministic<S,I,T,SP,TP> & net.automatalib.alphabet.SupportsGrowingAlphabet<I>>
extends AbstractLStar<A,I,D>
implements Resumable<AutomatonLStarState<I,D,AI,S>>

Abstract base class for algorithms that produce (subclasses of) MutableDeterministic automata.

This class provides the L*-style hypothesis construction. Implementing classes solely have to specify how state and transition properties should be derived.

Nested Class Summary

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

GlobalSuffixLearner.GlobalSuffixLearnerDFA<I>, GlobalSuffixLearner.GlobalSuffixLearnerMealy<I,O>

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

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

Nested classes/interfaces inherited from interface de.learnlib.datastructure.observationtable.OTLearner

OTLearner.OTLearnerDFA<I>, OTLearner.OTLearnerMealy<I,O>, OTLearner.OTLearnerMoore<I,O>

Field Summary

Fields

Modifier and Type	Field	Description
protected AI	internalHyp
protected net.automatalib.common.util.array.ArrayStorage<de.learnlib.algorithm.lstar.AbstractAutomatonLStar.StateInfo<S,I>>	stateInfos

Fields inherited from class de.learnlib.algorithm.lstar.AbstractLStar

alphabet, oracle, table

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	AbstractAutomatonLStar(net.automatalib.alphabet.Alphabet<I> alphabet, MembershipOracle<I,D> oracle, AI internalHyp)	Constructor.

Method Summary

Modifier and Type	Method	Description
void	addAlphabetSymbol(I symbol)
protected S	createState(boolean initial, Row<I> row)
protected void	doRefineHypothesis(DefaultQuery<I,D> ceQuery)
protected void	refineHypothesisInternal(DefaultQuery<I,D> ceQuery)
void	resume(AutomatonLStarState<I,D,AI,S> state)	Resume the datastructure from a previously suspended point in time.
protected void	setTransition(S from, I input, S to, Row<I> fromRow, int inputIdx)
void	startLearning()	Starts the model inference process, creating an initial hypothesis in the provided model object.
protected abstract SP	stateProperty(ObservationTable<I,D> table, Row<I> stateRow)	Derives a state property from the corresponding row.
AutomatonLStarState<I,D,AI,S>	suspend()	Expose the state object.
protected abstract TP	transitionProperty(ObservationTable<I,D> table, Row<I> stateRow, int inputIdx)	Derives a transition property from the corresponding transition.
protected void	updateInternalHypothesis()	Performs the L*-style hypothesis construction.

Methods inherited from class de.learnlib.algorithm.lstar.AbstractLStar

addGlobalSuffixes, analyzeInconsistency, completeConsistentTable, getGlobalSuffixes, getObservationTable, hypothesisOutput, incorporateCounterExample, initialPrefixes, initialSuffixes, refineHypothesis, selectClosingRows

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

internalHyp

protected AI extends net.automatalib.automaton.MutableDeterministic<S,I,T,SP,TP> & net.automatalib.alphabet.SupportsGrowingAlphabet<I> internalHyp

stateInfos

protected net.automatalib.common.util.array.ArrayStorage<de.learnlib.algorithm.lstar.AbstractAutomatonLStar.StateInfo<S,I>> stateInfos

Constructor Detail

AbstractAutomatonLStar

protected AbstractAutomatonLStar(net.automatalib.alphabet.Alphabet<I> alphabet,
                                 MembershipOracle<I,D> oracle,
                                 AI internalHyp)

Constructor.

Parameters:

alphabet - the learning alphabet

oracle - the learning oracle

internalHyp - the internal hypothesis object to write data to

Method Detail

startLearning

public final 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>

Overrides:

startLearning in class AbstractLStar<A,I,D>

updateInternalHypothesis

protected void updateInternalHypothesis()

Performs the L*-style hypothesis construction. For creating states and transitions, the stateProperty(ObservationTable, Row) and transitionProperty(ObservationTable, Row, int) methods are used to derive the respective properties.

stateProperty

protected abstract SP stateProperty(ObservationTable<I,D> table,
                                    Row<I> stateRow)

Derives a state property from the corresponding row.

Parameters:

table - the current observation table

stateRow - the row for which the state is created

Returns:

the state property of the corresponding state

createState

protected S createState(boolean initial,
                        Row<I> row)

setTransition

protected void setTransition(S from,
                             I input,
                             S to,
                             Row<I> fromRow,
                             int inputIdx)

transitionProperty

protected abstract TP transitionProperty(ObservationTable<I,D> table,
                                         Row<I> stateRow,
                                         int inputIdx)

Derives a transition property from the corresponding transition.

Note that not the transition row is passed to this method, but the row for the outgoing state. The transition row can be retrieved using Row.getSuccessor(int).

Parameters:

table - the observation table

stateRow - the row for the source state

inputIdx - the index of the input symbol to consider

Returns:

the transition property of the corresponding transition

doRefineHypothesis

protected final void doRefineHypothesis(DefaultQuery<I,D> ceQuery)

Overrides:

doRefineHypothesis in class AbstractLStar<A,I,D>

refineHypothesisInternal

protected void refineHypothesisInternal(DefaultQuery<I,D> ceQuery)

addAlphabetSymbol

public void addAlphabetSymbol(I symbol)

Specified by:

addAlphabetSymbol in interface net.automatalib.alphabet.SupportsGrowingAlphabet<A>

Overrides:

addAlphabetSymbol in class AbstractLStar<A,I,D>

suspend

public AutomatonLStarState<I,D,AI,S> suspend()

Description copied from interface: Resumable

Expose the state object.

Specified by:

suspend in interface Resumable<A>

Returns:

The state.

resume

public void resume(AutomatonLStarState<I,D,AI,S> 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.