Module de.learnlib.algorithm.lsharp

Package de.learnlib.algorithm.lsharp

Class LSharpMealy<I,O>

java.lang.Object

de.learnlib.algorithm.lsharp.LSharpMealy<I,O>

Type Parameters:

I - input symbol type

O - output symbol type

All Implemented Interfaces:

AccessSequenceTransformer<I>, LearningAlgorithm<MealyMachine<?,I,?,O>,I,Word<O>>, LearningAlgorithm.MealyLearner<I,O>, LearnerStateTracker

public class LSharpMealy<I,O>
extends Object
implements LearningAlgorithm.MealyLearner<I,O>, AccessSequenceTransformer<I>, LearnerStateTracker

Implementation of the L^# algorithm for MealyMachines. The implementation is based on the original implementation of the authors. However, it does not support all features (such as compressed ADSs or some of the more intricate equivalence checks on observation trees).

Implementation note: this learner uses the AccessSequenceTransformer interface to provide access to the representatives of the states of the current hypothesis model.

Nested Class Summary

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

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

Constructor Summary

Constructors

Constructor	Description
LSharpMealy(Alphabet<I> alphabet, AdaptiveMembershipOracle<I,O> oracle)
LSharpMealy(Alphabet<I> alphabet, AdaptiveMembershipOracle<I,O> oracle, Rule2 rule2, Rule3 rule3, @Nullable Word<I> sinkState, O sinkOutput, Random random)

Method Summary

Modifier and Type	Method	Description
CompactMealy<I,O>	buildHypothesis()
@Nullable DefaultQuery<I,Word<O>>	checkConsistency(MealyMachine<Integer,I,?,O> mealy)
void	checkFrontierConsistency()
CompactMealy<I,O>	constructHypothesis()
MealyMachine<?,I,?,O>	getHypothesisModel()	Returns the current hypothesis model.
boolean	hasLearningProcessStarted()	Returns whether the learning process has started yet.
Pair<Word<I>,Boolean>	identifyFrontierOrBasis(Word<I> seq)
void	initObsTree(@Nullable List<Pair<Word<I>,Word<O>>> logs)
void	makeObsTreeAdequate()
void	processBinarySearch(Word<I> ceInput, Word<O> ceOutput, MealyMachine<Integer,I,?,O> mealy)
boolean	processCex(DefaultQuery<I,Word<O>> cex, MealyMachine<Integer,I,?,O> mealy)
void	promoteFrontierState()
boolean	refineHypothesis(DefaultQuery<I,Word<O>> ceQuery)	Triggers a refinement of the model by providing a counterexample.
void	startLearning()	Starts the model inference process, creating an initial hypothesis in the provided model object.
Word<I>	transformAccessSequence(Word<I> word)
boolean	treeIsAdequate()
void	updateFrontierAndBasis()

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.learnlib.AccessSequenceTransformer

isAccessSequence, longestASPrefix

Methods inherited from interface de.learnlib.LearnerStateTracker

requireLearningProcessNotStarted, requireLearningProcessStarted

Constructor Details

LSharpMealy

public LSharpMealy(Alphabet<I> alphabet,
 AdaptiveMembershipOracle<I,O> oracle)

LSharpMealy

public LSharpMealy(Alphabet<I> alphabet,
 AdaptiveMembershipOracle<I,O> oracle,
 Rule2 rule2,
 Rule3 rule3,
 @Nullable Word<I> sinkState,
 O sinkOutput,
 Random random)

Method Details

processCex

public boolean processCex(DefaultQuery<I,Word<O>> cex,
 MealyMachine<Integer,I,?,O> mealy)

processBinarySearch

public void processBinarySearch(Word<I> ceInput,
 Word<O> ceOutput,
 MealyMachine<Integer,I,?,O> mealy)

makeObsTreeAdequate

public void makeObsTreeAdequate()

promoteFrontierState

public void promoteFrontierState()

treeIsAdequate

public boolean treeIsAdequate()

updateFrontierAndBasis

public void updateFrontierAndBasis()

buildHypothesis

public CompactMealy<I,O> buildHypothesis()

constructHypothesis

public CompactMealy<I,O> constructHypothesis()

identifyFrontierOrBasis

public Pair<Word<I>,Boolean> identifyFrontierOrBasis(Word<I> seq)

initObsTree

public void initObsTree(@Nullable List<Pair<Word<I>,Word<O>>> logs)

checkFrontierConsistency

public void checkFrontierConsistency()

checkConsistency

public @Nullable DefaultQuery<I,Word<O>> checkConsistency(MealyMachine<Integer,I,?,O> mealy)

startLearning

public void startLearning()

Description copied from interface: LearningAlgorithm

Starts the model inference process, creating an initial hypothesis in the provided model object.

Specified by:

startLearning in interface LearningAlgorithm<MealyMachine<?,I,?,O>,I,Word<O>>

refineHypothesis

public boolean refineHypothesis(DefaultQuery<I,Word<O>> 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.

Specified by:

refineHypothesis in interface LearningAlgorithm<MealyMachine<?,I,?,O>,I,Word<O>>

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 MealyMachine<?,I,?,O> 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 should not be modified by external code (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.

Specified by:

getHypothesisModel in interface LearningAlgorithm<MealyMachine<?,I,?,O>,I,Word<O>>

Returns:

the current hypothesis model.

hasLearningProcessStarted

public boolean hasLearningProcessStarted()

Description copied from interface: LearnerStateTracker

Returns whether the learning process has started yet.

Specified by:

hasLearningProcessStarted in interface LearnerStateTracker

Returns:

true if the learning process has started, false otherwise

transformAccessSequence

public Word<I> transformAccessSequence(Word<I> word)

Specified by:

transformAccessSequence in interface AccessSequenceTransformer<I>