Package net.automatalib.automaton.procedural

Interface SPA<S,I>

Type Parameters:

S - state type

I - input symbol type

All Superinterfaces:

AcceptorTS<S,I>, DeterministicAcceptorTS<S,I>, DeterministicTransitionSystem<S,I,S>, FiniteRepresentation, GraphViewable, InputAlphabetHolder<I>, Output<I,Boolean>, SimpleDTS<S,I>, SimpleTS<S,I>, SuffixOutput<I,Boolean>, TransitionSystem<S,I,S>, UniversalDTS<S,I,S,Boolean,Void>, UniversalTransitionSystem<S,I,S,Boolean,Void>

All Known Implementing Classes:

EmptySPA, StackSPA

public interface SPA<S,I>
extends DeterministicAcceptorTS<S,I>, SuffixOutput<I,Boolean>

A system of procedural automata. An SPA is a context-free system where each non-terminal (procedure) is represented by a DFA that accepts the language of right-hand sides of its respective production rules.

For example, take the following context-free palindrome system over a,b,c using two non-terminals F,G:

     F -> a | a F a | b | b F b | G | ε
     G -> c | c G c | F
 

The corresponding SPA would consist of procedures (for F and G), accepting the regular languages {a,aFa,b,bFb,G,ε} and {c,cGc,F} respectively.

In SPAs, calls to and returns from procedures are visible. For the above example, a possible word accepted by the respective SPA (when using F as initial procedure) would be FaFGcRRaR (where R denotes the designated return symbol.

For further information, see "Compositional learning of mutually recursive procedural systems".

This interface makes no assumptions about how the semantics are implemented. One may use a stack-based approach, graph expansion, or else. However, SPAs should be consistent with their alphabet definitions, i.e. an SPA should be able to parse words over the specified alphabet and each procedure should be able to parse words over the procedural inputs.

Method Summary

Modifier and Type	Method	Description
default Boolean	computeOutput(Iterable<? extends I> input)
@Nullable I	getInitialProcedure()	Returns the initial procedure (represented via its call symbol) of this system.
ProceduralInputAlphabet<I>	getInputAlphabet()	Refinement of InputAlphabetHolder.getInputAlphabet() to add the constraint that this system operates on ProceduralInputAlphabets.
default Collection<I>	getProceduralInputs()	Convenience method for getProceduralInputs(Collection) which uses the input alphabet of this system as constraints.
default Collection<I>	getProceduralInputs(Collection<I> constraints)
default @Nullable M	getProcedure(I callSymbol)	Convenience method for getProcedures() to quickly return the procedure of a given call symbol.
Map<I,M>	getProcedures()	Returns a Map from call symbols to the procedures of this system.
default Graph<?,?>	graphView()
default int	size()	Returns the size of this system which is given by the sum of the sizes of all procedures.

Methods inherited from interface net.automatalib.ts.acceptor.AcceptorTS

getStateProperty, getSuccessor, getTransitionProperty, isAccepting

Methods inherited from interface net.automatalib.ts.acceptor.DeterministicAcceptorTS

accepts, computeSuffixOutput, isAccepting

Methods inherited from interface net.automatalib.ts.DeterministicTransitionSystem

getSuccessor, getSuccessors, getTransition, getTransitions

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

getInitialState, getInitialStates, getState, getStates, getSuccessor, getSuccessors

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

createDynamicStateMapping, createStaticStateMapping, getSuccessors

Methods inherited from interface net.automatalib.ts.TransitionSystem

powersetView

Methods inherited from interface net.automatalib.ts.UniversalDTS

getTransitionProperty

Method Detail

getProceduralInputs

default Collection<I> getProceduralInputs(Collection<I> constraints)

computeOutput

default Boolean computeOutput(Iterable<? extends I> input)

Specified by:

computeOutput in interface DeterministicAcceptorTS<S,I>

Specified by:

computeOutput in interface Output<S,I>

Specified by:

computeOutput in interface SuffixOutput<S,I>

getInputAlphabet

ProceduralInputAlphabet<I> getInputAlphabet()

Refinement of InputAlphabetHolder.getInputAlphabet() to add the constraint that this system operates on ProceduralInputAlphabets.

Specified by:

getInputAlphabet in interface InputAlphabetHolder<I>

Returns:

the input alphabet

getProceduralInputs

default Collection<I> getProceduralInputs()

Convenience method for getProceduralInputs(Collection) which uses the input alphabet of this system as constraints.

Returns:

a collection of defined inputs for this system's procedures.

getInitialProcedure

@Nullable I getInitialProcedure()

Returns the initial procedure (represented via its call symbol) of this system.

Returns:

the initial procedure, may be null if undefined

getProcedures

Map<I,M> getProcedures()

Returns a Map from call symbols to the procedures of this system. Note that a (non-minimal) ProceduralSystem may not contain a procedure for every call symbol.

Returns:

the procedures of this system

getProcedure

default @Nullable M getProcedure(I callSymbol)

Convenience method for getProcedures() to quickly return the procedure of a given call symbol.

Parameters:

callSymbol - the call symbol

Returns:

the corresponding procedure. May be null if this system does not have a procedure for the given call symbol.

See Also:

getProcedures()

size

default int size()

Returns the size of this system which is given by the sum of the sizes of all procedures. Note that this value does not necessarily correspond to the classical notion of SimpleAutomaton.size(), since semantically a ProceduralSystem may be infinite-sized SimpleTS.

Specified by:

size in interface FiniteRepresentation

Returns:

the size of this system

graphView

default Graph<?,?> graphView()

Specified by:

graphView in interface GraphViewable