de.up.ling.irtg.algebra

Class BinarizingAlgebra<E>

java.lang.Object

de.up.ling.irtg.algebra.Algebra<E>

de.up.ling.irtg.algebra.BinarizingAlgebra<E>

Type Parameters:

E -

All Implemented Interfaces:

Serializable

Direct Known Subclasses:

BinarizingTagTreeAlgebra, BinarizingTagTreeWithAritiesAlgebra, BinarizingTreeAlgebra, BinarizingTreeWithAritiesAlgebra

public class BinarizingAlgebra<E>
extends Algebra<E>

An algebra with binarizing terms. Let A be some algebra of your choice. The binarizing algebra B is defined on top of the underlying algebra A as follows.

• The domain of B consists of lists of elements of the domain of A.
• If a/0 is a symbol in A, then a/0 is a symbol in B.
• If a/k for k > 0 is a symbol in A, then a/1 is a symbol in B.
• B contains a special symbol @/2 ("concatenation").
• B interprets a/0 as [|a|] and f/1 as the function that maps the list [t1,...,tn] to the singleton list [|f|(t1,...,tn)], where |a| and |f| are the interpretations of a/0 and f/n in A, respectively. @ denotes list concatenation.

The intended purpose of B is to provide binary terms that denote values in the domain of A. This is why in the implementation, BinarizingAlgebra is over the same type parameter for the domain as the underlying algebra A. The list values are only generated as intermediate results in evaluating an A-valued term.

By default, this algebra uses "_@_" for the concatenation symbol. You can specify your own symbol by passing it to the constructor.

Author:

koller

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
BinarizingAlgebra(Algebra<E> underlyingAlgebra) Create a new instance with _@_ as the concatenation symbol.
BinarizingAlgebra(Algebra<E> underlyingAlgebra, String appendSymbol) Create a new instance with a user specified concatenation symbol.

Method Summary

Modifier and Type	Method and Description
TreeAutomaton	binarizeTreeAutomaton(TreeAutomaton<? extends Object> underlyingAutomaton) Returns a tree automaton in which all rules are binarized by introducing intermediate rules with the concatenation symbol of this algebra.
TreeAutomaton	decompose(E value) Computes a decomposition automaton for the given value.
E	evaluate(Tree<String> t) Evaluates a term over the algebra's signature into an algebra object.
String	getAppendSymbol() Returns the concatenation symbol used by this algebra.
E	parseString(String representation) Resolves the string representation of some element of the algebra's domain to this element.

Methods inherited from class de.up.ling.irtg.algebra.Algebra

getAllAlgebraClasses, getClassOfValues, getSignature, hasOptions, readOptions, representAsString, setOptions, visualize, writeOptions

Methods inherited from class java.lang.Object

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

Constructor Detail

BinarizingAlgebra

public BinarizingAlgebra(Algebra<E> underlyingAlgebra)

Create a new instance with _@_ as the concatenation symbol. This algebra will use the underlying algebra to evaluate trees after removing the _@_ symbol.

Parameters:

underlyingAlgebra -

BinarizingAlgebra

public BinarizingAlgebra(Algebra<E> underlyingAlgebra,
                         String appendSymbol)

Create a new instance with a user specified concatenation symbol. This algebra will use the underlying algebra to evaluate trees after removing the _@_ symbol.

Parameters:

underlyingAlgebra -

appendSymbol -

Method Detail

getAppendSymbol

public String getAppendSymbol()

Returns the concatenation symbol used by this algebra.

Returns:

evaluate

public E evaluate(Tree<String> t)

Description copied from class: Algebra

Evaluates a term over the algebra's signature into an algebra object.

Overrides:

evaluate in class Algebra<E>

Parameters:

t - a term (= tree whose nodes are labeled with algebra operation symbols)

Returns:

binarizeTreeAutomaton

public TreeAutomaton binarizeTreeAutomaton(TreeAutomaton<? extends Object> underlyingAutomaton)

Returns a tree automaton in which all rules are binarized by introducing intermediate rules with the concatenation symbol of this algebra. This method is mainly intended to take decomposition automata from other algebras and turn them into decomposition automata for a Binarizing Algebra.

Parameters:

underlyingAutomaton -

Returns:

decompose

public TreeAutomaton decompose(E value)

Description copied from class: Algebra

Computes a decomposition automaton for the given value. A decomposition automaton is a finite tree automaton which accepts exactly those terms over the algebra's signature which evaluate to the given value.

Overrides:

decompose in class Algebra<E>

Returns:

parseString

public E parseString(String representation)
              throws ParserException

Description copied from class: Algebra

Resolves the string representation of some element of the algebra's domain to this element. For instance, the method TreeAlgebra.parseString(java.lang.String) resolves the string "f(a,b)" into a tree with three nodes.

It is the job of an algebra class to keep track of the signature of the algebra. Many algebras have a potentially infinite domain (e.g. the string algebra can be used with arbitrary alphabets), so the algebra class should keep track of the symbols that were actually used in the current run of the program. The best practice is to update the signature each time the parseString method is called. The rest of the IRTG tool code takes care to call parseString of the respective algebra to obtain objects of type E, so this ensures that the signature is always up-to-date.

Specified by:

parseString in class Algebra<E>

Returns:

Throws:

ParserException