de.learnlib.algorithms.features.observationtable

Interface ObservationTable<I,D>

Type Parameters:

I - input symbol type

D - observation (output) domain type

All Known Implementing Classes:

AbstractObservationTable, ObservationTable, SimpleObservationTable

@ParametersAreNonnullByDefault
public interface ObservationTable<I,D>

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

Nested Class Summary

Nested Classes

Modifier and Type	Interface and Description
static interface	ObservationTable.Inconsistency<I,D> Representation of an inconsistency in the observation table.
static interface	ObservationTable.Row<I,D> A single row in the observation table.

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

Methods

Modifier and Type	Method and Description
net.automatalib.words.Word<I>	findDistinguishingSuffix(ObservationTable.Inconsistency<I,D> inconsistency)
net.automatalib.words.Word<I>	findDistinguishingSuffix(ObservationTable.Row<I,D> firstRow, ObservationTable.Row<I,D> secondRow)
int	findDistinguishingSuffixIndex(ObservationTable.Inconsistency<I,D> inconsistency)
int	findDistinguishingSuffixIndex(ObservationTable.Row<I,D> firstRow, ObservationTable.Row<I,D> secondRow)
ObservationTable.Inconsistency<I,D>	findInconsistency(Collection<? extends I> inputs)
ObservationTable.Row<I,D>	findUnclosedRow()
Collection<? extends net.automatalib.words.Word<I>>	getAllPrefixes() Retrieves all prefixes (short and long) in the table.
Collection<? extends ObservationTable.Row<I,D>>	getAllRows()
Collection<? extends net.automatalib.words.Word<I>>	getLongPrefixes() Retrieves the long prefixes in the table.
Collection<? extends ObservationTable.Row<I,D>>	getLongPrefixRows()
ObservationTable.Row<I,D>	getRow(net.automatalib.words.Word<I> prefix)
Collection<? extends net.automatalib.words.Word<I>>	getShortPrefixes() Retrieves the short prefixes in the table.
Collection<? extends ObservationTable.Row<I,D>>	getShortPrefixRows()
ObservationTable.Row<I,D>	getSuccessorRow(ObservationTable.Row<I,D> spRow, I symbol)
net.automatalib.words.Word<I>	getSuffix(int index) Retrieves a suffix by its (column) index.
List<? extends net.automatalib.words.Word<I>>	getSuffixes() Retrieves all suffixes in the table.
boolean	isClosed()
boolean	isConsistent(Collection<? extends I> inputs)

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

getShortPrefixes

@Nonnull
Collection<? extends 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
Collection<? extends 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

getAllPrefixes

@Nonnull
Collection<? extends 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

getSuffixes

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

Retrieves all suffixes in the table.

Returns:

all suffixes in the table

getSuffix

@Nonnull
net.automatalib.words.Word<I> getSuffix(@Nonnegative
                                              int index)
                                        throws IndexOutOfBoundsException

Retrieves a suffix by its (column) index.

Parameters:

index -

Returns:

Throws:

IndexOutOfBoundsException

getShortPrefixRows

@Nonnull
Collection<? extends ObservationTable.Row<I,D>> getShortPrefixRows()

getLongPrefixRows

@Nonnull
Collection<? extends ObservationTable.Row<I,D>> getLongPrefixRows()

getAllRows

@Nonnull
Collection<? extends ObservationTable.Row<I,D>> getAllRows()

getRow

@Nonnull
ObservationTable.Row<I,D> getRow(net.automatalib.words.Word<I> prefix)
                                 throws NoSuchRowException

Throws:

NoSuchRowException

getSuccessorRow

@Nullable
ObservationTable.Row<I,D> getSuccessorRow(ObservationTable.Row<I,D> spRow,
                                                 @Nullable
                                                 I symbol)
                                          throws InvalidRowException

Throws:

InvalidRowException

isClosed

boolean isClosed()

findUnclosedRow

@Nullable
ObservationTable.Row<I,D> findUnclosedRow()

isConsistent

boolean isConsistent(Collection<? extends I> inputs)

findInconsistency

@Nullable
ObservationTable.Inconsistency<I,D> findInconsistency(Collection<? extends I> inputs)

findDistinguishingSuffixIndex

@Signed
int findDistinguishingSuffixIndex(ObservationTable.Inconsistency<I,D> inconsistency)
                                  throws NoSuchRowException,
                                         InvalidRowException

Parameters:

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

InvalidRowException

findDistinguishingSuffix

@Nullable
net.automatalib.words.Word<I> findDistinguishingSuffix(ObservationTable.Inconsistency<I,D> inconsistency)
                                                       throws NoSuchRowException,
                                                              InvalidRowException

Parameters:

inconsistency -

Returns:

Throws:

NoSuchRowException

InvalidRowException

findDistinguishingSuffixIndex

@Signed
int findDistinguishingSuffixIndex(ObservationTable.Row<I,D> firstRow,
                                       ObservationTable.Row<I,D> secondRow)
                                  throws InvalidRowException

Parameters:

firstRow - the first row

secondRow - 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

findDistinguishingSuffix

@Nullable
net.automatalib.words.Word<I> findDistinguishingSuffix(ObservationTable.Row<I,D> firstRow,
                                                              ObservationTable.Row<I,D> secondRow)
                                                       throws InvalidRowException

Parameters:

firstRow - the first row

secondRow - 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