Package de.learnlib.algorithm.adt.adt

Class ADT<S,I,O>

java.lang.Object

de.learnlib.algorithm.adt.adt.ADT<S,I,O>

Type Parameters:

S - (hypothesis) state type

I - input alphabet type

O - output alphabet type

public class ADT<S,I,O>
extends Object

The adaptive discrimination tree class. Essentially holds a reference to the root ADTNode and offers some utility methods used throughout the learning process.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	ADT.LCAInfo<S,I,O>

Constructor Summary

Constructors

Constructor	Description
ADT()

Method Summary

Modifier and Type	Method	Description
ADTNode<S,I,O>	extendLeaf(ADTNode<S,I,O> nodeToSplit, Word<I> distinguishingSuffix, Word<O> oldOutput, Word<O> newOutput, LeafSplitter leafSplitter)	Splitting a leaf node by extending the trace leading into the node to split.
ADT.LCAInfo<S,I,O>	findLCA(ADTNode<S,I,O> s1, ADTNode<S,I,O> s2)	Return the lowest common ancestor for the given two nodes.
ADTNode<S,I,O>	getRoot()	Returns the root node of this ADT.
void	initialize(S state)	Initializes the ADT with a single leaf node.
void	replaceNode(ADTNode<S,I,O> oldNode, ADTNode<S,I,O> newNode)	Replaces an existing node in the tree with a new one and updates the references of parent/child nodes accordingly.
ADTNode<S,I,O>	sift(SymbolQueryOracle<I,O> oracle, Word<I> word, ADTNode<S,I,O> subtree)	Successively sifts a word through the ADT induced by the given node.
ADTNode<S,I,O>	splitLeaf(ADTNode<S,I,O> nodeToSplit, Word<I> distinguishingSuffix, Word<O> oldOutput, Word<O> newOutput, LeafSplitter leafSplitter)	Splits a leaf node using a given LeafSplitter.

Methods inherited from class java.lang.Object

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

Constructor Detail

ADT

public ADT()

Method Detail

initialize

public void initialize(S state)

Initializes the ADT with a single leaf node.

Parameters:

state - the referenced state of the leaf

getRoot

public ADTNode<S,I,O> getRoot()

Returns the root node of this ADT.

Returns:

the root

replaceNode

public void replaceNode(ADTNode<S,I,O> oldNode,
                        ADTNode<S,I,O> newNode)

Replaces an existing node in the tree with a new one and updates the references of parent/child nodes accordingly.

Parameters:

oldNode - the node to replace

newNode - the replacement

sift

public ADTNode<S,I,O> sift(SymbolQueryOracle<I,O> oracle,
                                       Word<I> word,
                                       ADTNode<S,I,O> subtree)

Successively sifts a word through the ADT induced by the given node. Stops when reaching a leaf.

Parameters:

word - the word to sift

subtree - the node whose subtree is considered

Returns:

the leaf (see ADTNode.sift(SymbolQueryOracle, Word))

extendLeaf

public ADTNode<S,I,O> extendLeaf(ADTNode<S,I,O> nodeToSplit,
                                             Word<I> distinguishingSuffix,
                                             Word<O> oldOutput,
                                             Word<O> newOutput,
                                             LeafSplitter leafSplitter)

Splitting a leaf node by extending the trace leading into the node to split.

Parameters:

nodeToSplit - the leaf node to extends

distinguishingSuffix - the input sequence that splits the hypothesis state of the leaf to split and the new node. The current trace leading into the node to split must be a prefix of this word.

oldOutput - the hypothesis output of the node to split given the distinguishing suffix

newOutput - the hypothesis output of the new leaf given the distinguishing suffix

leafSplitter - the split strategy in case the root node needs to be split

Returns:

the new leaf node

splitLeaf

public ADTNode<S,I,O> splitLeaf(ADTNode<S,I,O> nodeToSplit,
                                            Word<I> distinguishingSuffix,
                                            Word<O> oldOutput,
                                            Word<O> newOutput,
                                            LeafSplitter leafSplitter)

Splits a leaf node using a given LeafSplitter.

Parameters:

nodeToSplit - the leaf node to split

distinguishingSuffix - the input sequence that splits the hypothesis state of the leaf to split and the new node

oldOutput - the hypothesis output of the node to split given the distinguishing suffix

newOutput - the hypothesis output of the new leaf given the distinguishing suffix

leafSplitter - the split strategy for leaves

Returns:

the new leaf node

findLCA

public ADT.LCAInfo<S,I,O> findLCA(ADTNode<S,I,O> s1,
                                              ADTNode<S,I,O> s2)

Return the lowest common ancestor for the given two nodes.

Parameters:

s1 - first node

s2 - second node

Returns:

A ADT.LCAInfo containing the lowest common ADTNode, the output determining the subtree of the first node and the output determining the subtree of the second node