Package de.learnlib.algorithm.adt.model

Class ObservationTree<S,​I,​O>

  • Type Parameters:
    S - (hypothesis) state type
    I - input alphabet type
    O - output alphabet type
    public class ObservationTree<S,​I,​O>
extends Object
    A class, that stores observations of the system under learning in a tree-like structure. Can be used to
    • Store output behavior information about the system under learning
    • Query output behavior of the system under learning if it has been stored before (i.e. cache)
    • Find separating words of hypothesis states based on the stored output behavior information

    • Constructor Detail

      • ObservationTree

        public ObservationTree​(Alphabet<I> alphabet)

    • Method Detail

      • getObservationTree

        public FastMealy<I,​O> getObservationTree()

      • initialize

        public void initialize​(S state)
        Initialize the observation tree with initial hypothesis state. Usually used during LearningAlgorithm.startLearning()
        Parameters:
        state - the initial state of the hypothesis

      • initialize

        public void initialize​(Collection<S> states,
                       Function<S,​Word<I>> asFunction,
                       Function<Word<I>,​Word<O>> outputFunction)
        Extended initialization method, that allows to initialize the observation tree with several hypothesis states.
        Parameters:
        states - The hypothesis states to initialize the observation tree with
        asFunction - Function to compute the access sequence of a node
        outputFunction - Function to compute the output of the access sequences

      • addTrace

        public void addTrace​(S state,
                     Word<I> input,
                     Word<O> output)
        Store input/output information about a hypothesis state in the internal data structure.
        Parameters:
        state - the hypothesis state for which information should be stored
        input - the input sequence applied when in the given state
        output - the observed output sequence

      • addTrace

        public void addTrace​(S state,
                     ADTNode<S,​I,​O> adtNode)
        See addState(Object, Word, Object). Convenience method that stores all information that the traces of the given ADTNode holds.
        Parameters:
        state - the hypothesis state for which information should be stored
        adtNode - the ADTNode whose traces should be stored

      • addState

        public void addState​(S newState,
                     Word<I> accessSequence,
                     O output)
        Registers a new hypothesis state at the observation tree. It is expected to register states in the order of their discovery, meaning whenever a new state is added, information about all prefixes of its access sequence are already stored. Therefore, providing only the output of the last symbol of its access sequence is sufficient.
        Parameters:
        newState - the hypothesis state in question
        accessSequence - the access sequence of the hypothesis state in the system under learning
        output - the output of the last symbol of the access sequence.

      • findSeparatingWord

        public Optional<Word<I>> findSeparatingWord​(S s1,
                                            S s2,
                                            Word<I> prefix)
        Find a separating word for two hypothesis states, after applying given input sequence first.
        Parameters:
        s1 - first state
        s2 - second state
        prefix - input sequence
        Returns:
        A Word separating the two states reached after applying the prefix to s1 and s2. Optional.empty() if not separating word exists.

      • findSeparatingWord

        public Word<I> findSeparatingWord​(S s1,
                                  S s2)
        Find a separating word for two hypothesis states.
        Parameters:
        s1 - first state
        s2 - second state
        Returns:
        A Word separating the two words. null if no such word is found.

      • trace

        public Word<O> trace​(S s,
                     Word<I> input)
        Computes the output of the system under learning when applying the given input sequence in the given hypothesis state. Requires the input/output behavior information to be stored before.
        Parameters:
        s - the hypothesis state
        input - the input sequence of interest
        Returns:
        the previously stored output behavior of the system under learning