de.learnlib.algorithms.lstargeneric

Class AbstractLStar<A,I,O>

java.lang.Object

de.learnlib.algorithms.lstargeneric.AbstractLStar<A,I,O>

Type Parameters:

A - automaton class.

I - input symbol class.

O - output class.

All Implemented Interfaces:

LearningAlgorithm<A,I,O>

Direct Known Subclasses:

AbstractAutomatonLStar

public abstract class AbstractLStar<A,I,O>
extends Object
implements LearningAlgorithm<A,I,O>

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.api.LearningAlgorithm

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

Field Summary

Fields

Modifier and Type	Field and Description
protected Alphabet<? extends I>	alphabet
protected MembershipOracle<I,O>	oracle
protected ObservationTable<I,O>	table

Constructor Summary

Constructors

Constructor and Description
AbstractLStar(Alphabet<I> alphabet, MembershipOracle<I,O> oracle) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected Word<I>	analyzeInconsistency(Inconsistency<I,O> incons) Analyzes an inconsistency.
protected void	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,O> ceQuery)
protected List<List<Row<I>>>	incorporateCounterExample(DefaultQuery<I,O> ce) Incorporates the information provided by a counterexample into the observation data structure.
protected abstract List<Word<I>>	initialSuffixes() Returns the list of initial suffixes which are used to initialize the table.
boolean	refineHypothesis(DefaultQuery<I,O> 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.LearningAlgorithm

getHypothesisModel

Field Detail

alphabet

protected final Alphabet<? extends I> alphabet

oracle

protected final MembershipOracle<I,O> oracle

table

protected final ObservationTable<I,O> table

Constructor Detail

AbstractLStar

public AbstractLStar(Alphabet<I> alphabet,
             MembershipOracle<I,O> oracle)

Constructor.

Parameters:

alphabet - the learning alphabet.

oracle - the membership oracle.

outputMapping - a mapping that translates between oracle outputs and data entries stored in the observation table.

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,O>

refineHypothesis

public final boolean refineHypothesis(DefaultQuery<I,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. Please note that invoking this method before an initial invocation of LearningAlgorithm.startLearning() should be illegal.

Specified by:

refineHypothesis in interface LearningAlgorithm<A,I,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).

doRefineHypothesis

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

completeConsistentTable

protected void 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.

analyzeInconsistency

protected Word<I> analyzeInconsistency(Inconsistency<I,O> 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

incorporateCounterExample

protected List<List<Row<I>>> incorporateCounterExample(DefaultQuery<I,O> 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.

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.

initialSuffixes

protected abstract List<Word<I>> initialSuffixes()

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

Returns:

the list of initial suffixes.