de.up.ling.irtg.binarization

Class StringAlgebraSeed

java.lang.Object

de.up.ling.irtg.binarization.RegularSeed

de.up.ling.irtg.binarization.StringAlgebraSeed

public class StringAlgebraSeed
extends RegularSeed

A regular seed for binarizing the WideStringAlgebra into the StringAlgebra. Each operation conck (for some number k) of the wide algebra is binarized as a tree automaton that describes all binary bracketings of the longer concatenation. For instance, the automaton for conc3 accepts the terms *(*(?1, ?2), ?3) and *(?1, *(?2, ?3)) over the ordinary string algebra.

Author:

koller

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	StringAlgebraSeed.OneSymbolAutomaton

Constructor Summary

Constructors

Constructor and Description
StringAlgebraSeed() This is only for technical reasons; don't use this constructor! Use #StringAlgebraSeed(de.up.ling.irtg.signature.Signature, java.lang.String) instead.
StringAlgebraSeed(Algebra sourceAlgebra, Algebra targetAlgebra)

Method Summary

Modifier and Type	Method and Description
TreeAutomaton	binarize(String symbol) Computes an automaton for all binarizations of a given symbol.

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

StringAlgebraSeed

public StringAlgebraSeed()

This is only for technical reasons; don't use this constructor! Use #StringAlgebraSeed(de.up.ling.irtg.signature.Signature, java.lang.String) instead.

StringAlgebraSeed

public StringAlgebraSeed(Algebra sourceAlgebra,
                         Algebra targetAlgebra)

Method Detail

binarize

public TreeAutomaton 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: