Package net.automatalib.incremental.dfa.tree

Class IncrementalDFATreeBuilder<I>

java.lang.Object

net.automatalib.incremental.dfa.AbstractIncrementalDFABuilder<I>

net.automatalib.incremental.dfa.tree.IncrementalDFATreeBuilder<I>

Type Parameters:

I - input symbol class

All Implemented Interfaces:

SupportsGrowingAlphabet<I>, InputAlphabetHolder<I>, IncrementalDFABuilder<I>, IncrementalConstruction<DFA<?,I>,I>

Direct Known Subclasses:

IncrementalPCDFATreeBuilder

public class IncrementalDFATreeBuilder<I>
extends AbstractIncrementalDFABuilder<I>

Incrementally builds a tree, from a set of positive and negative words. Using insert(Word, boolean), either the set of words definitely in the target language or definitely not in the target language is augmented. The lookup(Word) method then returns, for a given word, whether this word is in the set of definitely accepted words (Acceptance.TRUE), definitely rejected words (Acceptance.FALSE), or neither (Acceptance.DONT_KNOW).

Field Summary

Fields inherited from class net.automatalib.incremental.dfa.AbstractIncrementalDFABuilder

alphabetSize, inputAlphabet

Constructor Summary

Constructors

Constructor	Description
IncrementalDFATreeBuilder(Alphabet<I> inputAlphabet)

Method Summary

Modifier and Type	Method	Description
void	addAlphabetSymbol(I symbol)	Notifies the data structure that a new symbol should be added to the alphabet.
Graph<?,?>	asGraph()	Retrieves a graph view of the current state of the construction.
UniversalDTS<?,I,?,Acceptance,Void>	asTransitionSystem()	Retrieves a transition system view of the current state of the construction.
@Nullable Word<I>	findSeparatingWord(DFA<?,I> target, Collection<? extends I> inputs, boolean omitUndefined)	Checks the current state of the construction against a given target model, and returns a word exposing a difference if there is one.
void	insert(Word<? extends I> word, boolean acceptance)	Inserts a new word into the automaton, with a given acceptance value.
Acceptance	lookup(Word<? extends I> inputWord)	Looks up the tri-state acceptance value for a given word.

Methods inherited from class net.automatalib.incremental.dfa.AbstractIncrementalDFABuilder

getInputAlphabet

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.automatalib.incremental.dfa.IncrementalDFABuilder

hasDefinitiveInformation, insert

Constructor Detail

IncrementalDFATreeBuilder

public IncrementalDFATreeBuilder(Alphabet<I> inputAlphabet)

Method Detail

addAlphabetSymbol

public void addAlphabetSymbol(I symbol)

Description copied from interface: SupportsGrowingAlphabet

Notifies the data structure that a new symbol should be added to the alphabet. Behavior depends on the implementation:

• After adding a new symbol, the symbol-related data may either be initialized with default values or undefined.
• Duplicate symbols may: (1) be handled accordingly, (2) be ignored or (3) result in an error.

Some data structures may need to be properly initialized (e.g. with a GrowingAlphabet) to handle potentially shared state across multiple instances. If the needed requirements are not met, a GrowingAlphabetNotSupportedException can be thrown.

Specified by:

addAlphabetSymbol in interface SupportsGrowingAlphabet<I>

Overrides:

addAlphabetSymbol in class AbstractIncrementalDFABuilder<I>

Parameters:

symbol - the symbol to add to the alphabet.

findSeparatingWord

public @Nullable Word<I> findSeparatingWord(DFA<?,I> target,
                                            Collection<? extends I> inputs,
                                            boolean omitUndefined)

Description copied from interface: IncrementalConstruction

Checks the current state of the construction against a given target model, and returns a word exposing a difference if there is one.

Parameters:

target - the target automaton model

inputs - the set of input symbols to consider

omitUndefined - if this is set to true, then undefined transitions in the target model will be interpreted as "unspecified/don't know" and omitted in the equivalence test. Otherwise, they will be interpreted in the usual manner (e.g., non-accepting sink in case of DFAs).

Returns:

a separating word, or null if no difference could be found.

lookup

public Acceptance lookup(Word<? extends I> inputWord)

Description copied from interface: IncrementalDFABuilder

Looks up the tri-state acceptance value for a given word.

Parameters:

inputWord - the word

Returns:

the tri-state acceptance value for this word.

insert

public void insert(Word<? extends I> word,
                   boolean acceptance)

Description copied from interface: IncrementalDFABuilder

Inserts a new word into the automaton, with a given acceptance value.

Parameters:

word - the word to insert

acceptance - whether this word should be marked as accepting

asTransitionSystem

public UniversalDTS<?,I,?,Acceptance,Void> asTransitionSystem()

Description copied from interface: IncrementalConstruction

Retrieves a transition system view of the current state of the construction. The transition system model should be backed by the construction, i.e., subsequent changes will be reflected in the transition system.

Returns:

a transition system view on the current state of the construction

asGraph

public Graph<?,?> asGraph()

Description copied from interface: IncrementalConstruction

Retrieves a graph view of the current state of the construction. The graph model should be backed by the construction, i.e., subsequent changes will be reflected in the graph model.

Returns:

a graph view on the current state of the construction