net.automatalib.incremental.mealy

Class IncrementalMealyBuilder<I,O>

java.lang.Object

net.automatalib.ts.abstractimpl.AbstractTS<S,I,T>

net.automatalib.ts.abstractimpl.AbstractDTS<S,I,T>

net.automatalib.automata.abstractimpl.AbstractDeterministicAutomaton<State,I,TransitionRecord>

net.automatalib.incremental.mealy.IncrementalMealyBuilder<I,O>

Type Parameters:

I - input symbol class

O - output symbol class

All Implemented Interfaces:

Iterable<State>, Automaton<State,I,TransitionRecord>, TransitionOutput<TransitionRecord,O>, DeterministicAutomaton<State,I,TransitionRecord>, SimpleAutomaton<State,I>, SimpleDeterministicAutomaton<State,I>, DOTPlottableGraph<State,TransitionRecord>, Graph<State,TransitionRecord>, IndefiniteGraph<State,TransitionRecord>, UniversalGraph<State,TransitionRecord,Void,TransitionEdge.Property<I,O>>, UniversalIndefiniteGraph<State,TransitionRecord,Void,TransitionEdge.Property<I,O>>, IncrementalConstruction<MealyMachine<?,I,?,O>,I>, DeterministicTransitionSystem<State,I,TransitionRecord>, SimpleDTS<State,I>, SimpleTS<State,I>, TransitionSystem<State,I,TransitionRecord>

public class IncrementalMealyBuilder<I,O>
extends AbstractDeterministicAutomaton<State,I,TransitionRecord>
implements TransitionOutput<TransitionRecord,O>, UniversalGraph<State,TransitionRecord,Void,TransitionEdge.Property<I,O>>, DOTPlottableGraph<State,TransitionRecord>, IncrementalConstruction<MealyMachine<?,I,?,O>,I>

Incrementally builds an (acyclic) Mealy machine, from a set of input and corresponding output words.

Author:

Malte Isberner

Constructor Summary

Constructors

Constructor and Description
IncrementalMealyBuilder(Alphabet<I> inputAlphabet) Constructor.

Method Summary

Modifier and Type	Method and Description
<V> MutableMapping<State,V>	createDynamicNodeMapping()
<V> MutableMapping<State,V>	createStaticNodeMapping()
Word<I>	findSeparatingWord(MealyMachine<?,I,?,O> 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.
TransitionEdge.Property<I,O>	getEdgeProperty(TransitionRecord edge) Retrieves the property of a given edge.
GraphDOTHelper<State,TransitionRecord>	getGraphDOTHelper()
State	getInitialState() Retrieves the initial state of this transition system.
Alphabet<I>	getInputAlphabet() Retrieves the input alphabet of this construction.
Void	getNodeProperty(State node) Retrieves the property of a given node.
Collection<State>	getNodes() Retrieves an (unmodifiable) collection of the nodes in this graph.
Collection<TransitionRecord>	getOutgoingEdges(State node) Retrieves the outgoing edges of a given node.
Collection<State>	getStates() Retrieves all states of the transition system.
State	getSuccessor(TransitionRecord transition) Retrieves the successor state of a given transition.
State	getTarget(TransitionRecord edge) Retrieves, for a given edge, its target node.
TransitionRecord	getTransition(State state, I input) Retrieves the transition triggered by the given input symbol.
O	getTransitionOutput(TransitionRecord transition)
boolean	hasDefinitiveInformation(Word<I> word) Checks whether this class has definitive information about a given word.
void	insert(Word<I> word, Word<O> outputWord) Incorporates a pair of input/output words into the stored information.
boolean	isComplete(Word<I> word) Checks whether there exists secured information about the output for the given word.
boolean	lookup(Word<I> word, WordBuilder<O> output) Retrieves the output word for the given input word.
NodeIDs<State>	nodeIDs()
int	size() Retrieves the size (number of states) of this transition system.
CompactMealy<I,O>	toAutomaton() Creates an automaton model from the current state of the construction.

Methods inherited from class net.automatalib.automata.abstractimpl.AbstractDeterministicAutomaton

iterator, stateIDs

Methods inherited from class net.automatalib.ts.abstractimpl.AbstractDTS

getInitialStates, getInitialStates, getState, getState, getSuccessor, getSuccessor, getSuccessor, getSuccessor, getTransitions, getTransitions

Methods inherited from class net.automatalib.ts.abstractimpl.AbstractTS

createDynamicStateMapping, createDynamicStateMapping, createStaticStateMapping, createStaticStateMapping, getStates, getStates, getSuccessors, getSuccessors, getSuccessors, getSuccessors, getSuccessors, getSuccessors, powersetView, powersetView

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, iterator, spliterator

Methods inherited from interface net.automatalib.ts.TransitionSystem

getTransitions, powersetView

Methods inherited from interface net.automatalib.ts.simple.SimpleDTS

getState, getSuccessor, getSuccessor

Methods inherited from interface net.automatalib.ts.simple.SimpleTS

createDynamicStateMapping, createStaticStateMapping, getInitialStates, getStates, getSuccessors, getSuccessors, getSuccessors

Constructor Detail

IncrementalMealyBuilder

public IncrementalMealyBuilder(Alphabet<I> inputAlphabet)

Constructor.

Parameters:

inputAlphabet - the input alphabet to use

Method Detail

size

public int size()

Description copied from interface: SimpleAutomaton

Retrieves the size (number of states) of this transition system.

Specified by:

size in interface SimpleAutomaton<State,I>

Specified by:

size in interface Graph<State,TransitionRecord>

Overrides:

size in class AbstractDeterministicAutomaton<State,I,TransitionRecord>

Returns:

the number of states of this transition system

isComplete

public boolean isComplete(Word<I> word)

Checks whether there exists secured information about the output for the given word.

Parameters:

word - the input word

Returns:

a boolean indicating whether information about the output for the given input word exists.

lookup

public boolean lookup(Word<I> word,
                      WordBuilder<O> output)

Retrieves the output word for the given input word. If no definitive information for the input word exists, the output for the longest known prefix will be returned.

Parameters:

word - the input word

output - a WordBuilder for constructing the output word

Returns:

true if the information contained was complete (in this case, word.length() == output.size() will hold), false otherwise.

insert

public void insert(Word<I> word,
                   Word<O> outputWord)

Incorporates a pair of input/output words into the stored information.

Parameters:

word - the input word

outputWord - the corresponding output word

Throws:

ConflictException - if this information conflicts with information already stored

getSuccessor

public State getSuccessor(TransitionRecord transition)

Description copied from interface: TransitionSystem

Retrieves the successor state of a given transition.

Specified by:

getSuccessor in interface TransitionSystem<State,I,TransitionRecord>

Parameters:

transition - the transition.

Returns:

the successor state.

getInitialState

public State getInitialState()

Description copied from interface: SimpleDTS

Retrieves the initial state of this transition system.

Specified by:

getInitialState in interface SimpleDTS<State,I>

Returns:

the initial state.

See Also:

SimpleTS.getInitialStates()

getNodeProperty

public Void getNodeProperty(State node)

Description copied from interface: UniversalIndefiniteGraph

Retrieves the property of a given node.

Specified by:

getNodeProperty in interface UniversalIndefiniteGraph<State,TransitionRecord,Void,TransitionEdge.Property<I,O>>

Parameters:

node - the node

Returns:

the property of the specified node

getEdgeProperty

public TransitionEdge.Property<I,O> getEdgeProperty(TransitionRecord edge)

Description copied from interface: UniversalIndefiniteGraph

Retrieves the property of a given edge.

Specified by:

getEdgeProperty in interface UniversalIndefiniteGraph<State,TransitionRecord,Void,TransitionEdge.Property<I,O>>

Parameters:

edge - the edge

Returns:

the property of the specified edge

getOutgoingEdges

public Collection<TransitionRecord> getOutgoingEdges(State node)

Description copied from interface: IndefiniteGraph

Retrieves the outgoing edges of a given node.

Specified by:

getOutgoingEdges in interface IndefiniteGraph<State,TransitionRecord>

Parameters:

node - the node.

Returns:

a Collection of all outgoing edges, or null if the node has no outgoing edges.

getTarget

public State getTarget(TransitionRecord edge)

Description copied from interface: IndefiniteGraph

Retrieves, for a given edge, its target node.

Specified by:

getTarget in interface IndefiniteGraph<State,TransitionRecord>

Parameters:

edge - the edge.

Returns:

the target node of the given edge.

getTransitionOutput

public O getTransitionOutput(TransitionRecord transition)

Specified by:

getTransitionOutput in interface TransitionOutput<TransitionRecord,O>

getTransition

public TransitionRecord getTransition(State state,
                                      I input)

Description copied from interface: DeterministicTransitionSystem

Retrieves the transition triggered by the given input symbol.

Specified by:

getTransition in interface DeterministicTransitionSystem<State,I,TransitionRecord>

Parameters:

state - the source state.

input - the input symbol.

Returns:

the transition triggered by the given input symbol, or null if no transition is triggered.

See Also:

TransitionSystem.getTransitions(Object, Object)

getGraphDOTHelper

public GraphDOTHelper<State,TransitionRecord> getGraphDOTHelper()

Specified by:

getGraphDOTHelper in interface DOTPlottableGraph<State,TransitionRecord>

getStates

public Collection<State> getStates()

Description copied from interface: SimpleAutomaton

Retrieves all states of the transition system. Implementing classes should return an unmodifiable collection

Specified by:

getStates in interface SimpleAutomaton<State,I>

Returns:

all states in the transition system

getNodes

public Collection<State> getNodes()

Description copied from interface: Graph

Retrieves an (unmodifiable) collection of the nodes in this graph.

Specified by:

getNodes in interface Graph<State,TransitionRecord>

Returns:

the nodes in this graph

getInputAlphabet

public Alphabet<I> getInputAlphabet()

Description copied from interface: IncrementalConstruction

Retrieves the input alphabet of this construction.

Specified by:

getInputAlphabet in interface IncrementalConstruction<MealyMachine<?,I,?,O>,I>

Returns:

the input alphabet

findSeparatingWord

public Word<I> findSeparatingWord(MealyMachine<?,I,?,O> 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.

Specified by:

findSeparatingWord in interface IncrementalConstruction<MealyMachine<?,I,?,O>,I>

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.

toAutomaton

public CompactMealy<I,O> toAutomaton()

Description copied from interface: IncrementalConstruction

Creates an automaton model from the current state of the construction.

Specified by:

toAutomaton in interface IncrementalConstruction<MealyMachine<?,I,?,O>,I>

Returns:

an automaton model

hasDefinitiveInformation

public boolean hasDefinitiveInformation(Word<I> word)

Description copied from interface: IncrementalConstruction

Checks whether this class has definitive information about a given word.

Specified by:

hasDefinitiveInformation in interface IncrementalConstruction<MealyMachine<?,I,?,O>,I>

Parameters:

word - the word

Returns:

true if this class has definitive information about the word, false otherwise.

nodeIDs

public NodeIDs<State> nodeIDs()

Specified by:

nodeIDs in interface Graph<State,TransitionRecord>

createStaticNodeMapping

public <V> MutableMapping<State,V> createStaticNodeMapping()

Specified by:

createStaticNodeMapping in interface IndefiniteGraph<State,TransitionRecord>

createDynamicNodeMapping

public <V> MutableMapping<State,V> createDynamicNodeMapping()

Specified by:

createDynamicNodeMapping in interface IndefiniteGraph<State,TransitionRecord>