de.learnlib.datastructure.observationtable

Class GenericObservationTable<I,D>

java.lang.Object

de.learnlib.datastructure.observationtable.GenericObservationTable<I,D>

Type Parameters:

I - input symbol type

D - output domain type

All Implemented Interfaces:

AccessSequenceTransformer<I>, MutableObservationTable<I,D>, ObservationTable<I,D>, Serializable

public final class GenericObservationTable<I,D>
extends Object
implements MutableObservationTable<I,D>, Serializable

Observation table class.

An observation table (OT) is the central data structure used by Angluin's L* algorithm, as described in the paper "Learning Regular Sets from Queries and Counterexamples".

An observation table is a two-dimensional table, with rows indexed by prefixes, and columns indexed by suffixes. For a prefix u and a suffix v, the respective cell contains the result of the membership query (u, v).

The set of prefixes (row labels) is divided into two disjoint sets: short and long prefixes. Each long prefix is a one-letter extension of a short prefix; conversely, every time a prefix is added to the set of short prefixes, all possible one-letter extensions are added to the set of long prefixes.

In order to derive a well-defined hypothesis from an observation table, it must satisfy two properties: closedness and consistency.

• An observation table is closed iff for each long prefix u there exists a short prefix u' such that the row contents for both prefixes are equal.
• An observation table is consistent iff for every two short prefixes u and u' with identical row contents, it holds that for every input symbol a the rows indexed by ua and u'a also have identical contents.

Author:

Malte Isberner

See Also:

Serialized Form

Field Summary

Fields inherited from interface de.learnlib.datastructure.observationtable.ObservationTable

NO_DISTINGUISHING_SUFFIX

Constructor Summary

Constructors

Constructor and Description
GenericObservationTable(Alphabet<I> alphabet) Constructor.

Method Summary

Modifier and Type	Method and Description
List<List<Row<I>>>	addAlphabetSymbol(I symbol, MembershipOracle<I,D> oracle)
List<List<Row<I>>>	addShortPrefixes(List<? extends Word<I>> shortPrefixes, MembershipOracle<I,D> oracle)
List<List<Row<I>>>	addSuffix(Word<I> suffix, MembershipOracle<I,D> oracle) Adds a suffix to the list of distinguishing suffixes.
List<List<Row<I>>>	addSuffixes(Collection<? extends Word<I>> newSuffixes, MembershipOracle<I,D> oracle) Adds suffixes to the list of distinguishing suffixes.
Alphabet<I>	getInputAlphabet() Retrieves the input alphabet used in this observation table.
Collection<Row<I>>	getLongPrefixRows()
de.learnlib.datastructure.observationtable.RowImpl<I>	getRow(int rowId) Returns the specified row of the observation table.
List<Row<I>>	getShortPrefixRows()
List<Word<I>>	getSuffixes() Retrieves all suffixes in the table.
List<List<Row<I>>>	initialize(List<Word<I>> initialShortPrefixes, List<Word<I>> initialSuffixes, MembershipOracle<I,D> oracle) Initializes an observation table using a specified set of suffixes.
boolean	isAccessSequence(Word<I> word)
boolean	isInitialConsistencyCheckRequired()
boolean	isInitialized() Checks whether this observation table has been initialized yet (i.e., contains any rows).
int	numberOfDistinctRows() Returns the number of distinct (regarding row values) rows in this observation table.
int	numberOfRows() Returns the total number of rows in this observation table.
List<D>	rowContents(Row<I> row)
void	setInputAlphabet(Alphabet<I> alphabet) This is an internal method used for de-serializing.
List<List<Row<I>>>	toShortPrefixes(List<Row<I>> lpRows, MembershipOracle<I,D> oracle) Moves the specified rows to the set of short prefix rows.
Word<I>	transformAccessSequence(Word<I> word)

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.learnlib.datastructure.observationtable.ObservationTable

cellContents, findDistinguishingSuffix, findDistinguishingSuffix, findDistinguishingSuffixIndex, findDistinguishingSuffixIndex, findInconsistency, findUnclosedRow, getAllPrefixes, getAllRows, getLongPrefixes, getRow, getRowSuccessor, getShortPrefixes, getSuffix, isClosed, isConsistent, numberOfLongPrefixRows, numberOfShortPrefixRows, numberOfSuffixes

Methods inherited from interface de.learnlib.api.AccessSequenceTransformer

longestASPrefix

Constructor Detail

GenericObservationTable

public GenericObservationTable(Alphabet<I> alphabet)

Constructor.

Parameters:

alphabet - the learning alphabet.

Method Detail

initialize

public List<List<Row<I>>> initialize(List<Word<I>> initialShortPrefixes,
                                     List<Word<I>> initialSuffixes,
                                     MembershipOracle<I,D> oracle)

Description copied from interface: MutableObservationTable

Initializes an observation table using a specified set of suffixes.

Specified by:

initialize in interface MutableObservationTable<I,D>

initialSuffixes - the set of initial column labels.

oracle - the MembershipOracle to use for performing queries

Returns:

a list of equivalence classes of unclosed rows

numberOfDistinctRows

public int numberOfDistinctRows()

Description copied from interface: ObservationTable

Returns the number of distinct (regarding row values) rows in this observation table. This number may be used as the upper bound for the (content ids of the table rows.

Specified by:

numberOfDistinctRows in interface ObservationTable<I,D>

Returns:

the number of distinct rows

See Also:

Row.getRowContentId()

addSuffix

public List<List<Row<I>>> addSuffix(Word<I> suffix,
                                    MembershipOracle<I,D> oracle)

Description copied from interface: MutableObservationTable

Adds a suffix to the list of distinguishing suffixes. This is a convenience method that can be used as shorthand for addSufixes(Collections.singletonList(suffix), oracle).

Specified by:

addSuffix in interface MutableObservationTable<I,D>

Parameters:

suffix - the suffix to add

oracle - the membership oracle

Returns:

a list of equivalence classes of unclosed rows

addSuffixes

public List<List<Row<I>>> addSuffixes(Collection<? extends Word<I>> newSuffixes,
                                      MembershipOracle<I,D> oracle)

Description copied from interface: MutableObservationTable

Adds suffixes to the list of distinguishing suffixes.

Specified by:

addSuffixes in interface MutableObservationTable<I,D>

Parameters:

newSuffixes - the suffixes to add

oracle - the membership oracle

Returns:

a list of equivalence classes of unclosed rows

isInitialConsistencyCheckRequired

public boolean isInitialConsistencyCheckRequired()

Specified by:

isInitialConsistencyCheckRequired in interface MutableObservationTable<I,D>

addShortPrefixes

public List<List<Row<I>>> addShortPrefixes(List<? extends Word<I>> shortPrefixes,
                                           MembershipOracle<I,D> oracle)

Specified by:

addShortPrefixes in interface MutableObservationTable<I,D>

toShortPrefixes

public List<List<Row<I>>> toShortPrefixes(List<Row<I>> lpRows,
                                          MembershipOracle<I,D> oracle)

Description copied from interface: MutableObservationTable

Moves the specified rows to the set of short prefix rows. If some of the specified rows already are short prefix rows, they are ignored (unless they do not have any contents, in which case they are completed).

Specified by:

toShortPrefixes in interface MutableObservationTable<I,D>

Parameters:

lpRows - the rows to move to the set of short prefix rows

oracle - the membership oracle

Returns:

a list of equivalence classes of unclosed rows

rowContents

public List<D> rowContents(Row<I> row)

Specified by:

rowContents in interface ObservationTable<I,D>

getRow

public de.learnlib.datastructure.observationtable.RowImpl<I> getRow(int rowId)

Description copied from interface: ObservationTable

Returns the specified row of the observation table.

Specified by:

getRow in interface ObservationTable<I,D>

Parameters:

rowId - the index of the row

Returns:

the row

numberOfRows

public int numberOfRows()

Description copied from interface: ObservationTable

Returns the total number of rows in this observation table. This number may be used as the upper bound for the (row) ids of the table rows.

Specified by:

numberOfRows in interface ObservationTable<I,D>

Returns:

the number of rows

See Also:

Row.getRowId()

getSuffixes

public List<Word<I>> getSuffixes()

Description copied from interface: ObservationTable

Retrieves all suffixes in the table.

Specified by:

getSuffixes in interface ObservationTable<I,D>

Returns:

all suffixes in the table

isInitialized

public boolean isInitialized()

Description copied from interface: MutableObservationTable

Checks whether this observation table has been initialized yet (i.e., contains any rows).

Specified by:

isInitialized in interface MutableObservationTable<I,D>

Returns:

true iff the table has been initialized

getInputAlphabet

public Alphabet<I> getInputAlphabet()

Description copied from interface: ObservationTable

Retrieves the input alphabet used in this observation table.

Specified by:

getInputAlphabet in interface ObservationTable<I,D>

Returns:

the input alphabet

setInputAlphabet

public void setInputAlphabet(Alphabet<I> alphabet)

This is an internal method used for de-serializing. Do not deliberately set input alphabets.

Parameters:

alphabet - the input alphabet corresponding to the previously serialized one.

transformAccessSequence

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

Specified by:

transformAccessSequence in interface AccessSequenceTransformer<I>

isAccessSequence

public boolean isAccessSequence(Word<I> word)

Specified by:

isAccessSequence in interface AccessSequenceTransformer<I>

addAlphabetSymbol

public List<List<Row<I>>> addAlphabetSymbol(I symbol,
                                            MembershipOracle<I,D> oracle)

Specified by:

addAlphabetSymbol in interface MutableObservationTable<I,D>

getShortPrefixRows

public List<Row<I>> getShortPrefixRows()

Specified by:

getShortPrefixRows in interface ObservationTable<I,D>

getLongPrefixRows

public Collection<Row<I>> getLongPrefixRows()

Specified by:

getLongPrefixRows in interface ObservationTable<I,D>