Module de.learnlib.algorithm.ttt
Package de.learnlib.algorithm.ttt.base

Class AbstractTTTLearner<A,I,D>

java.lang.Object
de.learnlib.algorithm.ttt.base.AbstractTTTLearner<A,I,D>
Type Parameters:
A - hypothesis automaton type
I - input symbol type
D - output domain type
All Implemented Interfaces:
AccessSequenceTransformer<I>, LearningAlgorithm<A,I,D>, LearnerStateTracker, Resumable<TTTLearnerState<I,D>>, SupportsGrowingAlphabet<I>
Direct Known Subclasses:
TTTLearnerDFA, TTTLearnerMealy, TTTLearnerMoore
public abstract class AbstractTTTLearner<A,I,D> extends Object implements LearningAlgorithm<A,I,D>, AccessSequenceTransformer<I>, SupportsGrowingAlphabet<I>, Resumable<TTTLearnerState<I,D>>, LearnerStateTracker
The TTT learning algorithm for generic automata.

Implementation note: this learner uses the AccessSequenceTransformer interface to provide access to the representatives of the states of the current hypothesis model.

  • Field Details

  • Constructor Details

  • Method Details

    • link

      protected static <I, D> void link(AbstractBaseDTNode<I,D> dtNode, TTTState<I,D> state)
      Establish the connection between a node in the discrimination tree and a state of the hypothesis.
      Type Parameters:
      I - input symbol type
      D - output domain type
      Parameters:
      dtNode - the node in the discrimination tree
      state - the state in the hypothesis

    • startLearning

      public void startLearning()
      Description copied from interface: LearningAlgorithm
      Starts the model inference process, creating an initial hypothesis in the provided model object.
      Specified by:
      startLearning in interface LearningAlgorithm<A,I,D>

    • refineHypothesis

      public boolean refineHypothesis(DefaultQuery<I,D> ceQuery)
      Description copied from interface: LearningAlgorithm
      Triggers a refinement of the model by providing a counterexample. A counterexample is a query which exposes different behavior of the real SUL compared to the hypothesis.
      Specified by:
      refineHypothesis in interface LearningAlgorithm<A,I,D>
      Parameters:
      ceQuery - the query which exposes diverging behavior, as posed to the real SUL (i.e. with the SULs output).
      Returns:
      true if the counterexample triggered a refinement of the hypothesis, false otherwise (i.e., it was no counterexample).

    • hasLearningProcessStarted

      public boolean hasLearningProcessStarted()
      Description copied from interface: LearnerStateTracker
      Returns whether the learning process has started yet.
      Specified by:
      hasLearningProcessStarted in interface LearnerStateTracker
      Returns:
      true if the learning process has started, false otherwise

    • initializeState

      protected void initializeState(TTTState<I,D> state)
      Initializes a state. Creates its outgoing transition objects, and adds them to the "open" list.
      Parameters:
      state - the state to initialize

    • createTransition

      protected TTTTransition<I,D> createTransition(TTTState<I,D> state, I sym)

    • initTransitions

      protected void initTransitions(TTTTransition<I,D> head, int num)
      A post-processing hook for transitions created by createTransition(TTTState, Object), e.g., after initializeState(TTTState) or addAlphabetSymbol(Object). This is mainly useful for transition output hypotheses that want to initialize the transition outputs in a bulk operation.
      Parameters:
      head - the head of (the list of) the created transitions
      num - the number of created transitions

    • refineHypothesisSingle

      protected boolean refineHypothesisSingle(DefaultQuery<I,D> ceQuery)
      Performs a single refinement of the hypothesis, i.e., without repeated counterexample evaluation. The parameter and return value have the same significance as in refineHypothesis(DefaultQuery).
      Parameters:
      ceQuery - the counterexample (query) to be used for refinement
      Returns:
      true if the hypothesis was refined, false otherwise

    • deriveAcex

      protected OutInconsPrefixTransformAcex<I,D> deriveAcex(OutputInconsistency<I,D> outIncons)

    • succEffect

      protected abstract D succEffect(D effect)

    • finalizeAny

      protected boolean finalizeAny()
      Chooses a block root, and finalizes the corresponding discriminator.
      Returns:
      true if a splittable block root was found, false otherwise.

    • getDeterministicState

      protected TTTState<I,D> getDeterministicState(TTTState<I,D> start, Word<I> word)

    • getNonDetSuccessors

      protected Set<TTTState<I,D>> getNonDetSuccessors(Collection<? extends TTTState<I,D>> states, I sym)

    • getAnySuccessor

      protected TTTState<I,D> getAnySuccessor(TTTState<I,D> state, I sym)

    • getAnySuccessor

      protected TTTState<I,D> getAnySuccessor(TTTState<I,D> state, Iterable<? extends I> suffix)

    • getAnyTarget

      protected TTTState<I,D> getAnyTarget(TTTTransition<I,D> trans)
      Retrieves the target state of a given transition. This method works for both tree and non-tree transitions. If a non-tree transition points to a non-leaf node, it is updated accordingly before a result is obtained.
      Parameters:
      trans - the transition
      Returns:
      the target state of this transition (possibly after it having been updated)

    • findOutputInconsistency

      protected OutputInconsistency<I,D> findOutputInconsistency()

    • allNodesFinal

      protected boolean allNodesFinal()

    • declareFinal

      protected void declareFinal(AbstractBaseDTNode<I,D> blockRoot)

    • predictSuccOutcome

      protected abstract D predictSuccOutcome(TTTTransition<I,D> trans, AbstractBaseDTNode<I,D> succSeparator)

    • createMap

      protected <V> Map<D,V> createMap()

    • computeHypothesisOutput

      protected abstract D computeHypothesisOutput(TTTState<I,D> state, Word<I> suffix)

    • getHypothesisDS

      public AbstractTTTHypothesis<?,I,D,?> getHypothesisDS()

    • closeTransitions

      protected void closeTransitions()

    • makeTree

      protected TTTState<I,D> makeTree(TTTTransition<I,D> trans)

    • getDiscriminationTree

      public BaseTTTDiscriminationTree<I,D> getDiscriminationTree()
      Returns the discrimination tree.
      Returns:
      the discrimination tree

    • transformAccessSequence

      public Word<I> transformAccessSequence(Word<I> word)
      Specified by:
      transformAccessSequence in interface AccessSequenceTransformer<A>

    • addAlphabetSymbol

      public void addAlphabetSymbol(I symbol)
      Specified by:
      addAlphabetSymbol in interface SupportsGrowingAlphabet<A>

    • createNewNode

      protected abstract AbstractBaseDTNode<I,D> createNewNode(AbstractBaseDTNode<I,D> parent, D parentOutput)

    • suspend

      public TTTLearnerState<I,D> suspend()
      Description copied from interface: Resumable
      Expose the state object.
      Specified by:
      suspend in interface Resumable<A>
      Returns:
      The state.

    • resume

      public void resume(TTTLearnerState<I,D> state)
      Description copied from interface: Resumable
      Resume the data structure from a previously suspended point in time.
      Specified by:
      resume in interface Resumable<A>
      Parameters:
      state - The learner state.