Package de.learnlib.datastructure.observationtable

Class GenericObservationTable<I,​D>

  • Type Parameters:
    I - input symbol type
    D - output domain type
    All Implemented Interfaces:
    AccessSequenceTransformer<I>, MutableObservationTable<I,​D>, ObservationTable<I,​D>
    public final class GenericObservationTable<I,​D>
extends Object
implements MutableObservationTable<I,​D>
    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.