de.up.ling.irtg.binarization

Class IdentitySeed

java.lang.Object

de.up.ling.irtg.binarization.RegularSeed

de.up.ling.irtg.binarization.IdentitySeed

public class IdentitySeed
extends RegularSeed

A regular seed that implements the identity function. This seed "binarizes" each operation symbol f of arity n over the algebra to a tree automaton whose language is {f(?1,...,?n)}. It is really useful in case the signature of the algebra already consists of symbols of arity two or less; in these cases, one can use an IdentitySeed to indicate that no rewriting needs to be done on the algebra terms.

The IdentitySeed is not meant to be used with an algebra that contains symbols of higher arity. In those cases, the binarization may not actually have rank two.

Author:

koller

Constructor Summary

Constructors

Constructor and Description
IdentitySeed() This is only for technical reasons; don't use this constructor! Use IdentitySeed(de.up.ling.irtg.algebra.Algebra, de.up.ling.irtg.algebra.Algebra) instead.
IdentitySeed(Algebra sourceAlgebra, Algebra targetAlgebra)

Method Summary

Modifier and Type	Method and Description
TreeAutomaton<String>	binarize(String symbol) Computes an automaton for all binarizations of a given symbol.
static IdentitySeed	fromInterp(InterpretedTreeAutomaton irtg, String interpretation)

Methods inherited from class de.up.ling.irtg.binarization.RegularSeed

binarize, getAllRegularSeedClasses, printStats

Methods inherited from class java.lang.Object

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

Constructor Detail

IdentitySeed

public IdentitySeed()

This is only for technical reasons; don't use this constructor! Use IdentitySeed(de.up.ling.irtg.algebra.Algebra, de.up.ling.irtg.algebra.Algebra) instead.

IdentitySeed

public IdentitySeed(Algebra sourceAlgebra,
                    Algebra targetAlgebra)

Method Detail

binarize

public TreeAutomaton<String> binarize(String symbol)

Description copied from class: RegularSeed

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).

Specified by:

binarize in class RegularSeed

Returns:

fromInterp

public static IdentitySeed fromInterp(InterpretedTreeAutomaton irtg,
                                      String interpretation)