dpvis.dpProcessor
Class AbstractCSProcessor

java.lang.Object
  extended by dpvis.dpProcessor.AbstractCSProcessor
All Implemented Interfaces:
ContextSensitiveDpProcessor, DPProcessor, java.io.Serializable

public abstract class AbstractCSProcessor
extends java.lang.Object
implements ContextSensitiveDpProcessor

Abstract class implementing DPProcessor providing some utility methods for the generation of the html output of a concrete processor

Author:
felixs
See Also:
Serialized Form

Constructor Summary
AbstractCSProcessor()
           
 
Method Summary
protected static java.util.Set<java.util.Map<java.lang.String,java.util.List<java.lang.Integer>>> computeAllArgumentFilterings(java.util.List<Pair<java.lang.String,java.lang.Integer>> functions)
          Computes all possible argument filterings for the given function symbols.
static java.util.Set<Rule> computeGeneralizedUseableRules(RewriteSystem system, java.util.Set<java.lang.String> definedSymbols)
          Same as computeUsableRules, except that the depends relation is generalised.
static java.util.Set<Rule> computeUseableRules(RewriteSystem system, java.util.Set<java.lang.String> definedSymbols)
          Computes the usable rules for the given function symbols.
protected static void embedOrient(Rule rule)
          Tries do orient the given rule with an embedding orientation.
 void freeResources()
          Convenience implementation of the freeResources method that does actually nothing.
static java.util.Set<java.lang.String> getDefinedFunctions(java.util.Collection<Rule> rules, java.util.List<java.lang.String> allDefinedFunctions)
          Gets the defined function symbols that occur in the right hand side of one of the given rules.
static java.util.Set<java.lang.String> getForbiddenFunctions(java.util.Collection<Rule> rules)
           
 java.util.Map<java.lang.String,java.util.List<java.lang.String>> getParameterDescription()
          Default implementation for this method.
static boolean isStronglyConservative(Rule r)
           
protected static java.util.Set<java.util.List<java.lang.String>> lpoOrient(Rule rule, java.util.Set<java.util.List<java.lang.String>> ordering)
          Method to quickly orient a given rule by an LPO not violating the given precedence constraints (ordering).
 void setParameters(java.util.Map<java.lang.String,java.lang.String> params)
          Default implementation for this method.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface dpvis.dpProcessor.DPProcessor
getOutput, isComplete, process
 

Constructor Detail

AbstractCSProcessor

public AbstractCSProcessor()
Method Detail

lpoOrient

protected static java.util.Set<java.util.List<java.lang.String>> lpoOrient(Rule rule,
                                                                           java.util.Set<java.util.List<java.lang.String>> ordering)
                                                                    throws java.lang.Exception
Method to quickly orient a given rule by an LPO not violating the given precedence constraints (ordering). The implementation uses a heuristic, so it is not complete, though fast.

Parameters:
rule - The rule that shall be ordered.
ordering - The ordering constraints that must be considered. The constraints are actually a precedence on function symbols stored as set of lists of functions. Each list specifies specifies a sequence of decreasing function symbols. It is assumed the induced ordering is a partial ordering.
Returns:
A new precedence ordering that orients the rule: l > r, taking the given precedence constraints into account. If the given constraints formed a partial ordering, so does the output ordering.
Throws:
java.lang.Exception - In case the rule cannot be oriented when considering the given precedence constraints.

embedOrient

protected static void embedOrient(Rule rule)
                           throws java.lang.Exception
Tries do orient the given rule with an embedding orientation. If this fails the method throws an exception, otherwise it returns without any result.

Parameters:
rule - The rule that shall be oriented.
Throws:
java.lang.Exception - In case the rule cannot be oriented.

computeAllArgumentFilterings

protected static java.util.Set<java.util.Map<java.lang.String,java.util.List<java.lang.Integer>>> computeAllArgumentFilterings(java.util.List<Pair<java.lang.String,java.lang.Integer>> functions)
Computes all possible argument filterings for the given function symbols. Note that function symbols starting with a "U" are reserved for symbols introduced by unraveling transformations. For them restricted filterings are computed, i.e. only the first argument may be filtered. Use this function with caution. For bigger systems with many functions there may be many argument filterings.

Parameters:
functions - The functions for which the argument filterings shall be computed.
Returns:
A set of maps that map functions to filterings, i.e. lists of integers specifying those arguments of the function that are filtered, i.e. erased. A list may contain negative integers only if it contains exactly one element. In this case the filtering collapses terms with the function as root to the argument value provided by the absolute of the integer, i.e. f -> [-2] means that the filtering applied to the term f(x, y) is y.

getDefinedFunctions

public static java.util.Set<java.lang.String> getDefinedFunctions(java.util.Collection<Rule> rules,
                                                                  java.util.List<java.lang.String> allDefinedFunctions)
Gets the defined function symbols that occur in the right hand side of one of the given rules.

Parameters:
rules - The rules whose function symbols of the right-hand sides shall be taken.
allDefinedFunctions - The defined function symbols for which it shall be searched.
Returns:
The defined function symbols that occur in the right hand side of one of the given rules.

computeUseableRules

public static java.util.Set<Rule> computeUseableRules(RewriteSystem system,
                                                      java.util.Set<java.lang.String> definedSymbols)
Computes the usable rules for the given function symbols. These rules are the ones defining one of the given functions, or a function depending on such a function, where a function f depends on another function g if a rule defining g contains f in its right-hand side (of course the transitive closure of this relation is actually used).

Parameters:
system - The rewrite system whose usable rules shall be computed.
definedSymbols - The defined functions that are used to compute the usable rules.
Returns:
the usable rules.

computeGeneralizedUseableRules

public static java.util.Set<Rule> computeGeneralizedUseableRules(RewriteSystem system,
                                                                 java.util.Set<java.lang.String> definedSymbols)
Same as computeUsableRules, except that the depends relation is generalised. A function f depends on a function h if f = h or g depends on h and there is function l -> r such that root(l) = f and g occurs in r or non-replacing in l.

Parameters:
system - The rewrite system whose usable rules shall be computed.
definedSymbols - The defined functions that are used to compute the usable rules.
Returns:
The usable rules.

getForbiddenFunctions

public static java.util.Set<java.lang.String> getForbiddenFunctions(java.util.Collection<Rule> rules)

isStronglyConservative

public static boolean isStronglyConservative(Rule r)

freeResources

public void freeResources()
Convenience implementation of the freeResources method that does actually nothing. If your processor does not use any external resources it need not overwrite this method.

Specified by:
freeResources in interface DPProcessor

getParameterDescription

public java.util.Map<java.lang.String,java.util.List<java.lang.String>> getParameterDescription()
Default implementation for this method. Use this method (i.e. do not overwrite it) only if your custom processor does not provide any parameterisation.

Specified by:
getParameterDescription in interface DPProcessor
Returns:
A map describing possible parameters for this processor

setParameters

public void setParameters(java.util.Map<java.lang.String,java.lang.String> params)
Default implementation for this method. Use this method (i.e. do not overwrite it) only if your custom processor does not provide any parameterisation.

Specified by:
setParameters in interface DPProcessor
Parameters:
params - The parameters.