Module de.learnlib.algorithm.lstar

Package de.learnlib.algorithm.lstar.dfa

Class ExtensibleLStarDFA<I>

java.lang.Object

de.learnlib.algorithm.lstar.AbstractLStar<A,I,D>

de.learnlib.algorithm.lstar.AbstractAutomatonLStar<A,I,D,S,T,SP,TP,AI>

de.learnlib.algorithm.lstar.AbstractExtensibleAutomatonLStar<net.automatalib.automaton.fsa.DFA<?,I>,I,Boolean,Integer,Integer,Boolean,Void,net.automatalib.automaton.fsa.impl.CompactDFA<I>>

de.learnlib.algorithm.lstar.dfa.ExtensibleLStarDFA<I>

Type Parameters:

I - input symbol type

All Implemented Interfaces:

GlobalSuffixLearner<net.automatalib.automaton.fsa.DFA<?,I>,I,Boolean>, GlobalSuffixLearner.GlobalSuffixLearnerDFA<I>, LearningAlgorithm<net.automatalib.automaton.fsa.DFA<?,I>,I,Boolean>, LearningAlgorithm.DFALearner<I>, ObservationTableFeature<I,Boolean>, OTLearner<net.automatalib.automaton.fsa.DFA<?,I>,I,Boolean>, OTLearner.OTLearnerDFA<I>, Resumable<AutomatonLStarState<I,Boolean,net.automatalib.automaton.fsa.impl.CompactDFA<I>,Integer>>, net.automatalib.alphabet.SupportsGrowingAlphabet<I>

Direct Known Subclasses:

ClassicLStarDFA, MalerPnueliDFA, RivestSchapireDFA

public class ExtensibleLStarDFA<I>
extends AbstractExtensibleAutomatonLStar<net.automatalib.automaton.fsa.DFA<?,I>,I,Boolean,Integer,Integer,Boolean,Void,net.automatalib.automaton.fsa.impl.CompactDFA<I>>
implements OTLearner.OTLearnerDFA<I>, GlobalSuffixLearner.GlobalSuffixLearnerDFA<I>

An implementation of Angluin's L* algorithm for learning DFAs, as described in the paper "Learning Regular Sets from Queries and Counterexamples".

Nested Class Summary

Nested classes/interfaces inherited from class de.learnlib.algorithm.lstar.AbstractExtensibleAutomatonLStar

AbstractExtensibleAutomatonLStar.BuilderDefaults

Nested classes/interfaces inherited from interface de.learnlib.algorithm.GlobalSuffixLearner

GlobalSuffixLearner.GlobalSuffixLearnerDFA<I>, GlobalSuffixLearner.GlobalSuffixLearnerMealy<I,O>

Nested classes/interfaces inherited from interface de.learnlib.algorithm.LearningAlgorithm

LearningAlgorithm.DFALearner<I>, LearningAlgorithm.MealyLearner<I,O>, LearningAlgorithm.MooreLearner<I,O>, LearningAlgorithm.NFALearner<I>

Nested classes/interfaces inherited from interface de.learnlib.datastructure.observationtable.OTLearner

OTLearner.OTLearnerDFA<I>, OTLearner.OTLearnerMealy<I,O>, OTLearner.OTLearnerMoore<I,O>

Field Summary

Fields inherited from class de.learnlib.algorithm.lstar.AbstractExtensibleAutomatonLStar

cexHandler, closingStrategy, initialPrefixes, initialSuffixes

Fields inherited from class de.learnlib.algorithm.lstar.AbstractAutomatonLStar

internalHyp, stateInfos

Fields inherited from class de.learnlib.algorithm.lstar.AbstractLStar

alphabet, oracle, table

Constructor Summary

Constructors

Constructor	Description
ExtensibleLStarDFA(net.automatalib.alphabet.Alphabet<I> alphabet, MembershipOracle<I,Boolean> oracle, List<net.automatalib.word.Word<I>> initialSuffixes, ObservationTableCEXHandler<? super I,? super Boolean> cexHandler, ClosingStrategy<? super I,? super Boolean> closingStrategy)	Constructor.
ExtensibleLStarDFA(net.automatalib.alphabet.Alphabet<I> alphabet, MembershipOracle<I,Boolean> oracle, List<net.automatalib.word.Word<I>> initialPrefixes, List<net.automatalib.word.Word<I>> initialSuffixes, ObservationTableCEXHandler<? super I,? super Boolean> cexHandler, ClosingStrategy<? super I,? super Boolean> closingStrategy)

Method Summary

Modifier and Type	Method	Description
net.automatalib.automaton.fsa.DFA<?,I>	getHypothesisModel()	Returns the current hypothesis model.
protected net.automatalib.automaton.concept.SuffixOutput<I,Boolean>	hypothesisOutput()
protected Boolean	stateProperty(ObservationTable<I,Boolean> table, Row<I> stateRow)	Derives a state property from the corresponding row.
protected Void	transitionProperty(ObservationTable<I,Boolean> table, Row<I> stateRow, int inputIdx)	Derives a transition property from the corresponding transition.

Methods inherited from class de.learnlib.algorithm.lstar.AbstractExtensibleAutomatonLStar

initialPrefixes, initialSuffixes, refineHypothesisInternal, selectClosingRows

Methods inherited from class de.learnlib.algorithm.lstar.AbstractAutomatonLStar

addAlphabetSymbol, createState, doRefineHypothesis, resume, setTransition, startLearning, suspend, updateInternalHypothesis

Methods inherited from class de.learnlib.algorithm.lstar.AbstractLStar

addGlobalSuffixes, analyzeInconsistency, completeConsistentTable, getGlobalSuffixes, getObservationTable, incorporateCounterExample, refineHypothesis

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface de.learnlib.algorithm.GlobalSuffixLearner

addGlobalSuffixes, getGlobalSuffixes

Methods inherited from interface de.learnlib.algorithm.LearningAlgorithm

refineHypothesis, startLearning

Methods inherited from interface de.learnlib.datastructure.observationtable.ObservationTableFeature

getObservationTable

Constructor Detail

ExtensibleLStarDFA

public ExtensibleLStarDFA(net.automatalib.alphabet.Alphabet<I> alphabet,
                          MembershipOracle<I,Boolean> oracle,
                          List<net.automatalib.word.Word<I>> initialSuffixes,
                          ObservationTableCEXHandler<? super I,? super Boolean> cexHandler,
                          ClosingStrategy<? super I,? super Boolean> closingStrategy)

Constructor.

Parameters:

alphabet - the learning alphabet

oracle - the DFA oracle

initialSuffixes - the list of initial suffixes used in the observation table

cexHandler - the strategy for handling counterexamples

closingStrategy - the strategy for closing open rows of the observation table

ExtensibleLStarDFA

public ExtensibleLStarDFA(net.automatalib.alphabet.Alphabet<I> alphabet,
                          MembershipOracle<I,Boolean> oracle,
                          List<net.automatalib.word.Word<I>> initialPrefixes,
                          List<net.automatalib.word.Word<I>> initialSuffixes,
                          ObservationTableCEXHandler<? super I,? super Boolean> cexHandler,
                          ClosingStrategy<? super I,? super Boolean> closingStrategy)

Method Detail

getHypothesisModel

public net.automatalib.automaton.fsa.DFA<?,I> getHypothesisModel()

Description copied from interface: LearningAlgorithm

Returns the current hypothesis model.

N.B.: By the contract of this interface, the model returned by this method should not be modified by external code (i.e., M generally should refer to an immutable interface), and its validity is retained only until the next invocation of LearningAlgorithm.refineHypothesis(DefaultQuery). If older hypotheses have to be maintained, a copy of the returned model must be made.

Please note that it should be illegal to invoke this method before an initial invocation of LearningAlgorithm.startLearning().

Specified by:

getHypothesisModel in interface LearningAlgorithm<net.automatalib.automaton.fsa.DFA<?,I>,I,Boolean>

Returns:

the current hypothesis model.

stateProperty

protected Boolean stateProperty(ObservationTable<I,Boolean> table,
                                Row<I> stateRow)

Description copied from class: AbstractAutomatonLStar

Derives a state property from the corresponding row.

Specified by:

stateProperty in class AbstractAutomatonLStar<net.automatalib.automaton.fsa.DFA<?,I>,I,Boolean,Integer,Integer,Boolean,Void,net.automatalib.automaton.fsa.impl.CompactDFA<I>>

Parameters:

table - the current observation table

stateRow - the row for which the state is created

Returns:

the state property of the corresponding state

transitionProperty

protected Void transitionProperty(ObservationTable<I,Boolean> table,
                                  Row<I> stateRow,
                                  int inputIdx)

Description copied from class: AbstractAutomatonLStar

Derives a transition property from the corresponding transition.

Note that not the transition row is passed to this method, but the row for the outgoing state. The transition row can be retrieved using Row.getSuccessor(int).

Specified by:

transitionProperty in class AbstractAutomatonLStar<net.automatalib.automaton.fsa.DFA<?,I>,I,Boolean,Integer,Integer,Boolean,Void,net.automatalib.automaton.fsa.impl.CompactDFA<I>>

Parameters:

table - the observation table

stateRow - the row for the source state

inputIdx - the index of the input symbol to consider

Returns:

the transition property of the corresponding transition

hypothesisOutput

protected net.automatalib.automaton.concept.SuffixOutput<I,Boolean> hypothesisOutput()

Specified by:

hypothesisOutput in class AbstractLStar<net.automatalib.automaton.fsa.DFA<?,I>,I,Boolean>