Skip to content

Learning Algorithms in LearnLib

Jump to bottom
Malte Isberner edited this page Apr 10, 2014 · 1 revision

This page lists the learning algorithms currently implemented in LearnLib.

DFA Learning Algorithms

ExtensibleLStarDFA

Mealy Learning Algorithms

ExtensibleLStarMealy

  • Class Name: ExtensibleLStarMealy
  • Package Name: de.learnlib.algorithms.lstargeneric.mealy
  • Module: learnlib-lstar-generic
  • Type Parameters: I - input symbol type, O - output symbol type
  • Model Type: MealyMachine<?,I,?,O> - Mealy machine reading symbols of type I, and writing symbols of type O

This is the Mealy machine variant of the L* algorithm, as for instance described in the paper Inferring Mealy Machines. In its observation table it stores the suffix of the response corresponding to the suffix part of a membership query.

The name "Extensible" derives from the fact that several aspects which are only loosely specified (or unspecified) in the original presentations of the algorithms. These are:

  • Initial Suffixes: Classically, the alphabet (interpreted as one-letter words) is used to initialize the suffix set. Especially in case of large alphabets, this can lead to poor performance. The initial suffix set can be configured freely, even the empty set is allowed and leads to valid results.
  • Closing Strategy: If multiple rows can fix an unclosedness, this decides which of them is moved to the upper part of the table.
  • Counterexample Handling: Specifies how counterexamples are treated in the refineHypothesis method. The standard procedure is the one described by Angluin, but also other (mostly suffix-based) procedures can be specified here.

ClassicLStarMealy

  • Class Name: ClasicLStarMealy
  • Package Name: de.learnlib.algorithms.lstargeneric.mealy
  • Module: learnlib-lstar-generic
  • Type Parameters: I - input symbol type, O - output symbol type
  • Model Type: MealyMachine<?,I,?,O> - Mealy machine reading symbols of type I, and writing symbols of type O

This algorithm closely resembles the above ExtensibleLStarMealy, with the important difference that it stores only the last symbol of the observed response in the cells of the observation table (as presented in the paper Introduction to Automata Learning from a Practical Perspective). This may lead to improved memory and runtime performance, but may result in a larger number of required membership queries being required.

This has the following API-level implications, which constitute differences to other Mealy machine learning algorithms:

  1. The oracle has to be of type MembershipOracle<I,O> instead of MembershipOracle<I,Word<O>>. The former can be obtained from the latter through the method MealyUtil.wrapWordOracle(MembershipOracle<I,Word<O>>) (package de.learnlib.mealy, module learnlib-core).
  2. The refineHypothesis method takes a DefaultQuery<I,O> instead of a DefaultQuery<I,Word<O>>. The former can be obtained from the latter through the method MealyUtil.reduceCounterExample(DefaultQuery<I,Word<O>>) (package de.learnlib.mealy, module learnlib-core) To align a ClassicLStarMealy learner object with the usual interface of Mealy machine learning algorithms (i.e., addressing item 2 above), such a learner object can be passed to the method MealyUtil.wrapSymbolLearner(LearningAlgorithm<M,I,O>) (package de.learnlib.mealy, module learnlib-core) in order to obtain a LearningAlgorithm<M,I,Word<O>> object whose refineHypothesis method expects a DefaultQuery<I,Word<O>>.
Clone this wiki locally