Package 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
    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.

    • Method Detail

      • getInputAlphabet

        Alphabet<I> getInputAlphabet()
        Retrieves the input alphabet used in this observation table.
        Returns:
        the input alphabet

      • getAllPrefixes

        default Collection<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

        default Collection<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

        default Collection<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

      • getRow

        Row<I> getRow​(int idx)
        Returns the specified row of the observation table.
        Parameters:
        idx - the index of the row
        Returns:
        the row
        Throws:
        IndexOutOfBoundsException - if idx is less than 0 or greater than number of rows - 1.

      • getRow

        default @Nullable Row<I> getRow​(Word<I> prefix)

      • 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

        default @Nullable Row<I> findUnclosedRow()

      • findDistinguishingSuffix

        default @Nullable Word<I> findDistinguishingSuffix​(Inconsistency<I> inconsistency)

      • findDistinguishingSuffix

        default @Nullable 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

      • findDistinguishingSuffixIndex

        default @org.checkerframework.checker.signedness.qual.Signed 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.

      • findDistinguishingSuffixIndex

        default @org.checkerframework.checker.signedness.qual.Signed 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.

      • getSuffix

        default Word<I> getSuffix​(int index)
        Retrieves a suffix by its (column) index.
        Parameters:
        index - the index
        Returns:
        the suffix

      • getSuffixes

        List<Word<I>> getSuffixes()
        Retrieves all suffixes in the table.
        Returns:
        all suffixes in the table

      • numberOfSuffixes

        default int numberOfSuffixes()

      • isConsistent

        default boolean isConsistent()

      • findInconsistency

        default @Nullable Inconsistency<I> findInconsistency()

      • getRowSuccessor

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

      • rowContents

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

      • cellContents

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