de.learnlib.algorithms.lstar

Class AbstractLStar<A,I,D>

java.lang.Object

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

Type Parameters:

A - automaton type

I - input symbol type

D - output domain type

All Implemented Interfaces:

GlobalSuffixFeature<I>, GlobalSuffixLearner<A,I,D>, SupportsGrowingAlphabet<I>, LearningAlgorithm<A,I,D>, ObservationTableFeature<I,D>, OTLearner<A,I,D>

Direct Known Subclasses:

AbstractAutomatonLStar

public abstract class AbstractLStar<A,I,D>
extends Object
implements OTLearner<A,I,D>, GlobalSuffixLearner<A,I,D>, SupportsGrowingAlphabet<I>

An abstract base class for L*-style algorithms.

This class implements basic management features (table, alphabet, oracle) and the main loop of alternating completeness and consistency checks. It does not take care of choosing how to initialize the table and hypothesis construction.

Author:

Malte Isberner

Nested Class Summary

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

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

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

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

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 net.automatalib.words.Alphabet<I>	alphabet
protected MembershipOracle<I,D>	oracle
protected GenericObservationTable<I,D>	table

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	AbstractLStar(net.automatalib.words.Alphabet<I> alphabet, MembershipOracle<I,D> oracle) Constructor.

Method Summary

Modifier and Type	Method and Description
void	addAlphabetSymbol(I symbol)
boolean	addGlobalSuffixes(Collection<? extends net.automatalib.words.Word<I>> newGlobalSuffixes) Add the provided suffixes to the collection of global suffixes.
protected net.automatalib.words.Word<I>	analyzeInconsistency(Inconsistency<I> incons) Analyzes an inconsistency.
protected boolean	completeConsistentTable(List<List<Row<I>>> unclosed, boolean checkConsistency) Iteratedly checks for unclosedness and inconsistencies in the table, and fixes any occurrences thereof.
protected void	doRefineHypothesis(DefaultQuery<I,D> ceQuery)
Collection<net.automatalib.words.Word<I>>	getGlobalSuffixes() Retrieves the global suffixes of this learner.
ObservationTable<I,D>	getObservationTable()
protected abstract net.automatalib.automata.concepts.SuffixOutput<I,D>	hypothesisOutput()
protected List<List<Row<I>>>	incorporateCounterExample(DefaultQuery<I,D> ce) Incorporates the information provided by a counterexample into the observation data structure.
protected List<net.automatalib.words.Word<I>>	initialPrefixes()
protected abstract List<net.automatalib.words.Word<I>>	initialSuffixes() Returns the list of initial suffixes which are used to initialize the table.
boolean	refineHypothesis(DefaultQuery<I,D> ceQuery) Triggers a refinement of the model by providing a counterexample.
protected List<Row<I>>	selectClosingRows(List<List<Row<I>>> unclosed) This method selects a set of rows to use for closing the table.
void	startLearning() Starts the model inference process, creating an initial hypothesis in the provided model 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.api.algorithm.LearningAlgorithm

getHypothesisModel

Field Detail

alphabet

protected net.automatalib.words.Alphabet<I> alphabet

oracle

protected final MembershipOracle<I,D> oracle

table

protected GenericObservationTable<I,D> table

Constructor Detail

AbstractLStar

protected AbstractLStar(net.automatalib.words.Alphabet<I> alphabet,
                        MembershipOracle<I,D> oracle)

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

refineHypothesis

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

hypothesisOutput

protected abstract net.automatalib.automata.concepts.SuffixOutput<I,D> hypothesisOutput()

doRefineHypothesis

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

incorporateCounterExample

protected List<List<Row<I>>> incorporateCounterExample(DefaultQuery<I,D> ce)

Incorporates the information provided by a counterexample into the observation data structure.

Parameters:

ce - the query which contradicts the hypothesis

Returns:

the rows (equivalence classes) which became unclosed by adding the information.

initialPrefixes

protected List<net.automatalib.words.Word<I>> initialPrefixes()

initialSuffixes

protected abstract List<net.automatalib.words.Word<I>> initialSuffixes()

Returns the list of initial suffixes which are used to initialize the table.

Returns:

the list of initial suffixes.

completeConsistentTable

protected boolean completeConsistentTable(List<List<Row<I>>> unclosed,
                                          boolean checkConsistency)

Iteratedly checks for unclosedness and inconsistencies in the table, and fixes any occurrences thereof. This process is repeated until the observation table is both closed and consistent.

Parameters:

unclosed - the unclosed rows (equivalence classes) to start with.

selectClosingRows

protected List<Row<I>> selectClosingRows(List<List<Row<I>>> unclosed)

This method selects a set of rows to use for closing the table. It receives as input a list of row lists, such that each (inner) list contains long prefix rows with (currently) identical contents, which have no matching short prefix row. The outer list is the list of all those equivalence classes.

Parameters:

unclosed - a list of equivalence classes of unclosed rows.

Returns:

a list containing a representative row from each class to move to the short prefix part.

analyzeInconsistency

protected net.automatalib.words.Word<I> analyzeInconsistency(Inconsistency<I> incons)

Analyzes an inconsistency. This analysis consists in determining the column in which the two successor rows differ.

Parameters:

incons - the inconsistency description

Returns:

the suffix to add in order to fix the inconsistency

getGlobalSuffixes

public Collection<net.automatalib.words.Word<I>> getGlobalSuffixes()

Description copied from interface: GlobalSuffixFeature

Retrieves the global suffixes of this learner. Calling this method before LearningAlgorithm.startLearning() should return an empty collection.

The return value should not be modified; attempting to do so may result in an UnsupportedOperationException. It is the implementation's responsibility to ensure attempted modifications do not corrupt the learner's internal state.

Specified by:

getGlobalSuffixes in interface GlobalSuffixFeature<I>

Returns:

the global suffixes used by this algorithm

addGlobalSuffixes

public boolean addGlobalSuffixes(Collection<? extends net.automatalib.words.Word<I>> newGlobalSuffixes)

Description copied from interface: GlobalSuffixFeature

Add the provided suffixes to the collection of global suffixes. As this method is designed to possibly trigger a refinement, it is illegal to invoke it before LearningAlgorithm.startLearning() has been called.

The implementation may choose to (but is not required to) omit suffixes which are already present (that is, manage the global suffixes as a proper set).

Specified by:

addGlobalSuffixes in interface GlobalSuffixFeature<I>

Parameters:

newGlobalSuffixes - the global suffixes to add

Returns:

true if a refinement was triggered by adding the global suffixes, false otherwise.

getObservationTable

public ObservationTable<I,D> getObservationTable()

Specified by:

getObservationTable in interface ObservationTableFeature<I,D>

addAlphabetSymbol

public void addAlphabetSymbol(I symbol)

Specified by:

addAlphabetSymbol in interface SupportsGrowingAlphabet<I>