Clone wiki

alto / 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.

The Algebra Interface and Writing your Own Algebra

This portion of the wiki is under construction, please contact us if you have any questions.