de.learnlib.datastructure.observationtable

Interface ObservationTable<I,D>

Type Parameters:

I - input symbol type

D - observation (output) domain type

All Superinterfaces:

AccessSequenceTransformer<I>

All Known Subinterfaces:

MutableObservationTable<I,D>

All Known Implementing Classes:

GenericObservationTable, SimpleObservationTable

@ParametersAreNonnullByDefault
public interface ObservationTable<I,D>
extends AccessSequenceTransformer<I>

An observation table is a common method for learning algorithms to store organize their observations. This interface defines a generic API for interacting with homogeneously interacting with observation tables regardless of their implementation.

Instances implementing this interface can be obtained from learning algorithms implementing the observation table feature (or OTLearners.

Basically, an observation table is a two-dimensional table, where both rows and columns are indexed by Words. The row indices are called prefixes, whereas the column indexes are referred to as suffixes. The table is further vertically divided into two halves: the prefixes in the upper half are referred to as short prefixes (these usually correspond to states in learned hypothesis automata), whereas the prefixes in the lower half are referred to as long prefixes. Long prefixes must be one-letter extensions of short prefixes; they refer to transitions in the hypothesis automaton. We refer to rows as short prefix rows or long prefix row, depending on whether they occur in the upper or lower half of the table respectively.

The cells of the table are filled with observations for a given prefix and suffix combination. The type of observations is generic and can be specified using the type parameter O.

There are two important properties of observation tables, which usually have to be satisfied in order to be able to generate an automaton from an observation table: it must be both closed and consistent.

In a closed observation table, the contents of each long prefix row equal the contents of at least one short prefix rows. Consistency, on the other hand, is satisfied when for every two distinct short prefix rows, all rows indexed by one-letter extensions of the corresponding prefix with any input symbol also have the same content.

Author:

Malte Isberner

Field Summary

Fields

Modifier and Type	Field and Description
static int	NO_DISTINGUISHING_SUFFIX Used to indicate that no distinguishing suffix exists in findDistinguishingSuffixIndex(Inconsistency) and findDistinguishingSuffixIndex(Row, Row).

Method Summary

Modifier and Type	Method and Description
D	cellContents(Row<I> row, int columnId)
default net.automatalib.words.Word<I>	findDistinguishingSuffix(Inconsistency<I> inconsistency)
default net.automatalib.words.Word<I>	findDistinguishingSuffix(Row<I> row1, Row<I> row2)
default int	findDistinguishingSuffixIndex(Inconsistency<I> inconsistency)
default int	findDistinguishingSuffixIndex(Row<I> row1, Row<I> row2)
default Inconsistency<I>	findInconsistency()
default Row<I>	findUnclosedRow()
default Collection<net.automatalib.words.Word<I>>	getAllPrefixes() Retrieves all prefixes (short and long) in the table.
default Collection<Row<I>>	getAllRows()
net.automatalib.words.Alphabet<I>	getInputAlphabet() Retrieves the input alphabet used in this observation table.
default Collection<net.automatalib.words.Word<I>>	getLongPrefixes() Retrieves the long prefixes in the table.
Collection<Row<I>>	getLongPrefixRows()
Row<I>	getRow(int idx)
default Row<I>	getRow(net.automatalib.words.Word<I> prefix)
default Row<I>	getRowSuccessor(Row<I> row, I sym)
default Collection<net.automatalib.words.Word<I>>	getShortPrefixes() Retrieves the short prefixes in the table.
Collection<Row<I>>	getShortPrefixRows()
default net.automatalib.words.Word<I>	getSuffix(int index) Retrieves a suffix by its (column) index.
List<net.automatalib.words.Word<I>>	getSuffixes() Retrieves all suffixes in the table.
default boolean	isClosed()
default boolean	isConsistent()
int	numberOfDistinctRows() Returns the number of distinct (regarding row values) rows in this observation table.
default int	numberOfLongPrefixRows()
default int	numberOfRows() Returns the total number of rows in this observation table.
default int	numberOfShortPrefixRows()
default int	numberOfSuffixes()
List<D>	rowContents(Row<I> row)

Methods inherited from interface de.learnlib.api.AccessSequenceTransformer

isAccessSequence, longestASPrefix, transformAccessSequence

Field Detail

NO_DISTINGUISHING_SUFFIX

static final int NO_DISTINGUISHING_SUFFIX

Used to indicate that no distinguishing suffix exists in findDistinguishingSuffixIndex(Inconsistency) and findDistinguishingSuffixIndex(Row, Row).

See Also:

Constant Field Values

Method Detail

getInputAlphabet

net.automatalib.words.Alphabet<I> getInputAlphabet()

Retrieves the input alphabet used in this observation table.

Returns:

the input alphabet

getAllPrefixes

@Nonnull
default Collection<net.automatalib.words.Word<I>> getAllPrefixes()

Retrieves all prefixes (short and long) in the table. The prefixes are returned in no specified order.

Returns:

all prefixes in the table

getShortPrefixes

@Nonnull
default Collection<net.automatalib.words.Word<I>> getShortPrefixes()

Retrieves the short prefixes in the table. The prefixes are returned in no specified order.

Returns:

the short prefixes in the table

getLongPrefixes

@Nonnull
default Collection<net.automatalib.words.Word<I>> getLongPrefixes()

Retrieves the long prefixes in the table. The prefixes are returned in no specified order.

Returns:

the long prefixes in the table

getShortPrefixRows

@Nonnull
Collection<Row<I>> getShortPrefixRows()

getLongPrefixRows

@Nonnull
Collection<Row<I>> getLongPrefixRows()

getRow

@Nullable
Row<I> getRow(int idx)

getRow

@Nullable
default Row<I> getRow(net.automatalib.words.Word<I> prefix)

getAllRows

@Nonnull
default Collection<Row<I>> getAllRows()

numberOfRows

default int numberOfRows()

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.

Returns:

the number of rows

See Also:

Row.getRowId()

numberOfShortPrefixRows

default int numberOfShortPrefixRows()

numberOfLongPrefixRows

default int numberOfLongPrefixRows()

numberOfDistinctRows

int numberOfDistinctRows()

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.

Returns:

the number of distinct rows

See Also:

Row.getRowContentId()

isClosed

default boolean isClosed()

findUnclosedRow

@Nullable
default Row<I> findUnclosedRow()

findDistinguishingSuffix

@Nullable
default net.automatalib.words.Word<I> findDistinguishingSuffix(Inconsistency<I> inconsistency)

findDistinguishingSuffix

@Nullable
default net.automatalib.words.Word<I> findDistinguishingSuffix(Row<I> row1,
                                                                         Row<I> row2)

Parameters:

row1 - the first row

row2 - the second row

Returns:

the suffix distinguishing the contents of the two rows

Throws:

InvalidRowException - if the rows do not belong to this observation table

findDistinguishingSuffixIndex

@Signed
default int findDistinguishingSuffixIndex(Inconsistency<I> inconsistency)

Returns:

the suffix (column) index where the contents of the rows differ, or #NO_DISTINGUISHING_SUFFIX if the contents of the rows are equal.

Throws:

NoSuchRowException - if the

findDistinguishingSuffixIndex

@Signed
default int findDistinguishingSuffixIndex(Row<I> row1,
                                                  Row<I> row2)

Parameters:

row1 - the first row

row2 - the second row

Returns:

the suffix (column) index where the contents of the rows differ, or #NO_DISTINGUISHING_SUFFIX if the contents of the rows are equal.

Throws:

InvalidRowException - if the rows do not belong to this observation table

getSuffix

@Nonnull
default net.automatalib.words.Word<I> getSuffix(int index)

Retrieves a suffix by its (column) index.

Parameters:

index - the index

Returns:

the suffix

getSuffixes

@Nonnull
List<net.automatalib.words.Word<I>> getSuffixes()

Retrieves all suffixes in the table.

Returns:

all suffixes in the table

numberOfSuffixes

default int numberOfSuffixes()

isConsistent

default boolean isConsistent()

findInconsistency

@Nullable
default Inconsistency<I> findInconsistency()

getRowSuccessor

default Row<I> getRowSuccessor(Row<I> row,
                               I sym)

rowContents

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

cellContents

D cellContents(Row<I> row,
               int columnId)