Interface SPA<S,I>
-
- Type Parameters:
S
- state typeI
- 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>
public interface SPA<S,I> extends DeterministicAcceptorTS<S,I>, SuffixOutput<I,Boolean>
A system of procedural automata. AnSPA
is a context-free system where each non-terminal (procedure) is represented by aDFA
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-terminalsF,G
:F -> a | a F a | b | b F b | G | ε G -> c | c G c | F
The correspondingSPA
would consist ofprocedures
(forF
andG
), accepting the regular languages{a,aFa,b,bFb,G,ε}
and{c,cGc,F}
respectively.In
SPA
s, calls to and returns from procedures are visible. For the above example, a possible word accepted by the respectiveSPA
(when usingF
asinitial procedure
) would beFaFGcRRaR
(whereR
denotes the designatedreturn 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,
SPA
s should be consistent with their alphabet definitions, i.e. anSPA
should be able toparse
words over thespecified alphabet
and eachprocedure
should be able toparse
words over theprocedural inputs
.
-
-
Method Summary
All Methods Instance Methods Abstract Methods Default Methods Modifier and Type Method Description default Boolean
computeOutput(Iterable<? extends I> input)
@Nullable I
getInitialProcedure()
Returns the initial procedure (represented via itscall symbol
) of this system.ProceduralInputAlphabet<I>
getInputAlphabet()
Refinement ofInputAlphabetHolder.getInputAlphabet()
to add the constraint thatthis
system operates onProceduralInputAlphabet
s.default Collection<I>
getProceduralInputs()
Convenience method forgetProceduralInputs(Collection)
which uses theinput alphabet
ofthis
system asconstraints
.default Collection<I>
getProceduralInputs(Collection<I> constraints)
default @Nullable M
getProcedure(I callSymbol)
Convenience method forgetProcedures()
to quickly return the procedure of a given call symbol.Map<I,M>
getProcedures()
default Graph<?,?>
graphView()
default int
size()
Returns the size ofthis
system which is given by the sum of the sizes of allprocedures
.-
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 interfaceDeterministicAcceptorTS<S,I>
- Specified by:
computeOutput
in interfaceOutput<S,I>
- Specified by:
computeOutput
in interfaceSuffixOutput<S,I>
-
getInputAlphabet
ProceduralInputAlphabet<I> getInputAlphabet()
Refinement ofInputAlphabetHolder.getInputAlphabet()
to add the constraint thatthis
system operates onProceduralInputAlphabet
s.- Specified by:
getInputAlphabet
in interfaceInputAlphabetHolder<I>
- Returns:
- the input alphabet
-
getProceduralInputs
default Collection<I> getProceduralInputs()
Convenience method forgetProceduralInputs(Collection)
which uses theinput alphabet
ofthis
system asconstraints
.- Returns:
- a collection of defined inputs for
this
system's procedures.
-
getInitialProcedure
@Nullable I getInitialProcedure()
Returns the initial procedure (represented via itscall symbol
) of this system.- Returns:
- the initial procedure, may be
null
if undefined
-
getProcedures
Map<I,M> getProcedures()
Returns aMap
fromcall symbols
to the procedures ofthis
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 forgetProcedures()
to quickly return the procedure of a given call symbol.- Parameters:
callSymbol
- the call symbol- Returns:
- the corresponding procedure. May be
null
ifthis
system does not have a procedure for the given call symbol. - See Also:
getProcedures()
-
size
default int size()
Returns the size ofthis
system which is given by the sum of the sizes of allprocedures
. Note that this value does not necessarily correspond to the classical notion ofSimpleAutomaton.size()
, since semantically aProceduralSystem
may be infinite-sizedSimpleTS
.- Specified by:
size
in interfaceFiniteRepresentation
- Returns:
- the size of
this
system
-
graphView
default Graph<?,?> graphView()
- Specified by:
graphView
in interfaceGraphViewable
-
-