de.up.ling.irtg.binarization

Class RegularSeed

java.lang.Object

de.up.ling.irtg.binarization.RegularSeed

Direct Known Subclasses:

BinarizingAlgebraSeed, IdentitySeed, StringAlgebraSeed

public abstract class RegularSeed
extends Object

A mapping from the operations of one algebra into terms consisting of operations of another algebra. A regular seed R maps each symbol f over the input algebra to a tree automaton R(f), defined by the (abstract) binarize(java.lang.String) method. The expected behavior of R(f) is that L(R(f)) consists of a set of terms over the output algebra such that the interpretation of these terms in the output algebra is the same as the interpretation of f in the input algebra.

Author:

koller

Constructor Summary

Constructors

Constructor and Description
RegularSeed()

Method Summary

Modifier and Type	Method and Description
abstract TreeAutomaton<String>	binarize(String symbol) Computes an automaton for all binarizations of a given symbol.
TreeAutomaton<String>	binarize(Tree<String> term) Computes an automaton for all binarizations of a given term.
static Iterator<Class>	getAllRegularSeedClasses() Returns an iterator over all subclasses of RegularSeed.
void	printStats()

Methods inherited from class java.lang.Object

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

Constructor Detail

RegularSeed

public RegularSeed()

Method Detail

binarize

public abstract TreeAutomaton<String> binarize(String symbol)

Computes an automaton for all binarizations of a given symbol. If f is a k-place symbol, then each binarization is a term that contains each variable symbol ?1, ..., ?k exactly once. The intended use of these automata is that every term accepted by the automaton evaluates to the same function over some given algebra as the original k-place symbol (but expresses this function using symbols of lower arity).

The automaton returned by this method must satisfy a number of requirements.

• The automaton has exactly one final state.
• There is no state that expands both into a variable (i.e. there is a rule q -> ?i) and into a terminal symbol (i.e. there is a rule q -> f(q1,...,qn) where f is not of the form ?i).

Parameters:

symbol -

Returns:

binarize

public TreeAutomaton<String> binarize(Tree<String> term)

Computes an automaton for all binarizations of a given term. This automaton is obtained from the binarizations of the individual symbols by tree automaton substitution. That is, the binarization of f(t1,...,tn) contains all the rules from the binarizations of f and all t1,...,tn. The states of these automata are renamed apart, and connected in the following way. If the binarization automaton for f contains a rule q -> ?i (i.e., the i-th variable), then all occurrences of q in the automaton are replaced by the final state of the binarization automaton for ti.

Parameters:

term -

Returns:

getAllRegularSeedClasses

public static Iterator<Class> getAllRegularSeedClasses()

Returns an iterator over all subclasses of RegularSeed.

Returns:

printStats

public void printStats()