Algebras

Algebras

Algebras are the workhorse of the IRTG framework implemented in Alto, because they allow us to use IRTG grammars to represent a large range of possible objects -- e.g., strings, trees, graphs, and so on -- and of relations between them.

Technically, an algebra A = (A, f1, ..., fn, I) is a collection of some set A, some set of operation symbols f1, ..., fn, and an interpretation function I. Each operation symbol f is assigned an arity ar(f). The operation symbols with their arities make up the signature of the algebra A.

The interpretation function maps each symbol f of arity k to a k-place function I(f):A x ... x A -> A. In particular, 0-ary symbols (aka constants) are mapped to elements of A; 1-ary symbols are mapped to unary functions; and so on. We define the terms over A as all trees over the signature. The interpretation function extends to terms in the obvious way, yielding a function that evaluates terms over the signature to values in A.

An IRTG generates a set of derivation trees and maps them to terms over some algebra, where they are then evaluated. See Koller & Kuhlmann 2011 for the technical details.

The following algebras are implemented in Alto. In the third column, we list the grammar formalism that an IRTG over this algebra represents.

Class	Description	Formalism
StringAlgebra	Strings with binary concatenation	context-free grammars
WideStringAlgebra	Strings with arbitrary-width concatenation	context-free grammars
TagStringAlgebra	Strings and string pairs with concatenation and wrapping operations, suitable for representing tree-adjoining grammars	TAG (strings)
TreeAlgebra	Trees with k-place tree construction f(t1,...,tk)	regular tree languages
TreeWithAritiesAlgebra	Trees with operations that permit the same node label to appear with different numbers of children
TagTreeAlgebra	Trees and tree pairs with YIELD operations, suitable for representing tree-adjoining grammars	TAG (derived trees)
SetAlgebra	Subsets of and relations over a given universe, with some set operations
GraphAlgebra	Graphs and s-graphs, with the operations of the HR-algebra (merge, rename, forget)	Hyperedge Replacement Grammars

Using an IRTG with multiple interpretations, you can represent synchronous or transducer-like grammar formalisms. For instance, a grammar with two StringAlgebra interpretations is an SCFG; a grammar with two TreeAlgebra interpretations is a bottom-up tree transducer; a grammar with a StringAlgebra and a GraphAlgebra interpretation is a synchronous HRG; and so on.

Below, we explain some of the key algebras. You can also find more details in the Apidocs of the individual algebras, behind the links. We will then explain how you can implement your own algebra and use Alto to define grammars over it.

String Algebra

This is an algebra over Lists of atomic words (strings). Its constants are all possible strings (there is no explicit set of constants, when the algebra sees a string in the position of a constant, it simply considers it as such). Its only operation is binary concatenation. The lists of strings that form the domain are generally rendered as plain text string i.e. ['a','b','c'] becomes "a b c" in the GUI.

Writing your Own Algebra

You can extend Alto with your own algebras. This will allow you to write IRTG grammars which use your algebra. In order to define a new algebra, write a class that extends the abstract base class Algebra and make sure it is in your classpath.

A minimal algebra class implements the abstract methods evaluate, which interprets the symbols of the algebra's signature as functions from values of the algebra to values of the algebra, and parseString, which maps string representations of values in the algebra to the values themselves.

You are welcome to override any of the other methods as well. For instance, you might want to replace the default implementation of decompose, which returns relatively inefficient decomposition automata which only support bottom-up queries for rules, with a specialized method that exploits specific details of your algebra (see e.g. how the StringAlgebra does this). You can also change the representAsString and visualize methods to render the values of your algebra in a more human-readable form.