Type information

As mentioned previously the AG formalism allows for a word acceptor automaton W that accepts only a regular subset of all possible path names as being legal. This can be used to restrict certain pointers from certain locations, for example we may not want the root node of a tree to have a parent pointer, although all the other nodes will need one. However, we can use this word acceptor automaton to allow different types of nodes. Rather than have a homogeneous structure, where each node must have the same number of outgoing pointers, we allow each node to have a type that determines the number and names of such pointers. Thus we can nest the structures defined, and have a list of trees, built from descriptions of a tree and list.



Timothy Lewis
1998-09-18