Package de.learnlib.algorithm.lstar

Class AbstractLStar<A,​I,​D>

    • Constructor Detail

      • AbstractLStar

        protected AbstractLStar​(Alphabet<I> alphabet,
                        MembershipOracle<I,​D> oracle)
        Constructor.
        Parameters:
        alphabet - the learning alphabet.
        oracle - the membership oracle.

    • Method Detail

      • startLearning

        public void startLearning()
        Description copied from interface: LearningAlgorithm
        Starts the model inference process, creating an initial hypothesis in the provided model object. Please note that it should be illegal to invoke this method twice.
        Specified by:
        startLearning in interface LearningAlgorithm<A,​I,​D>

      • refineHypothesis

        public final 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. Please note that invoking this method before an initial invocation of LearningAlgorithm.startLearning() should be illegal.
        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).

      • hypothesisOutput

        protected abstract SuffixOutput<I,​D> hypothesisOutput()

      • doRefineHypothesis

        protected void doRefineHypothesis​(DefaultQuery<I,​D> ceQuery)

      • incorporateCounterExample

        protected List<List<Row<I>>> incorporateCounterExample​(DefaultQuery<I,​D> ce)
        Incorporates the information provided by a counterexample into the observation data structure.
        Parameters:
        ce - the query which contradicts the hypothesis
        Returns:
        the rows (equivalence classes) which became unclosed by adding the information.

      • initialPrefixes

        protected List<Word<I>> initialPrefixes()

      • initialSuffixes

        protected abstract List<Word<I>> initialSuffixes()
        Returns the list of initial suffixes which are used to initialize the table.
        Returns:
        the list of initial suffixes.

      • completeConsistentTable

        protected boolean completeConsistentTable​(List<List<Row<I>>> unclosed,
                                          boolean checkConsistency)
        Iteratedly checks for unclosedness and inconsistencies in the table, and fixes any occurrences thereof. This process is repeated until the observation table is both closed and consistent.
        Parameters:
        unclosed - the unclosed rows (equivalence classes) to start with.

      • selectClosingRows

        protected List<Row<I>> selectClosingRows​(List<List<Row<I>>> unclosed)
        This method selects a set of rows to use for closing the table. It receives as input a list of row lists, such that each (inner) list contains long prefix rows with (currently) identical contents, which have no matching short prefix row. The outer list is the list of all those equivalence classes.
        Parameters:
        unclosed - a list of equivalence classes of unclosed rows.
        Returns:
        a list containing a representative row from each class to move to the short prefix part.

      • analyzeInconsistency

        protected Word<I> analyzeInconsistency​(Inconsistency<I> incons)
        Analyzes an inconsistency. This analysis consists in determining the column in which the two successor rows differ.
        Parameters:
        incons - the inconsistency description
        Returns:
        the suffix to add in order to fix the inconsistency

      • addGlobalSuffixes

        public boolean addGlobalSuffixes​(Collection<? extends Word<I>> newGlobalSuffixes)
        Description copied from interface: GlobalSuffixLearner
        Add the provided suffixes to the collection of global suffixes. As this method is designed to possibly trigger a refinement, it is illegal to invoke it before LearningAlgorithm.startLearning() has been called.

        The implementation may choose to (but is not required to) omit suffixes which are already present (that is, manage the global suffixes as a proper set).

        Specified by:
        addGlobalSuffixes in interface GlobalSuffixLearner<A,​I,​D>
        Parameters:
        newGlobalSuffixes - the global suffixes to add
        Returns:
        true if a refinement was triggered by adding the global suffixes, false otherwise.