-
Notifications
You must be signed in to change notification settings - Fork 2
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
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.
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.