Related work

ASAP

The description consists of a set of axioms that describe when nodes can be aliased or are disjoint. The axioms are based on regular expressions in the direction symbols.

Graph Types

The structure is a tree with additional routing pointers, defined by expressions. The routing expressions are regular expressions over the directions, with additional terms that allow the expressions to test the type of the current node.

Group Fields

The group is described by a presentation, a list of equations that summarise all the possible cycles in its graph. This is a very general description and may include structures where we cannot determine whether two nodes are linked by a particular direction (a situation related to the word problem. Analysis of such structures would have to work on a restricted subset of these groups.

Shape Types

The structure is represented by a list of triples, where a pointer name precedes the pair of nodes that it links. A grammar gives the structure of the list. Certain questions that we can answer cleanly for Automatic Groups may not be readily solved for these structures, since the context-free languages are more general than regular languages.

Recursive Tree Programs

[Fea98] This work looks at dependencies in a class of programs using rational transducers as the framework. These are similar, but more general than the two-variable FSAs we use here. The generality implies that certain manipulations produce problems that are undecidable, and a semi-algorithm is proposed as a partial solution. Also the only data structures considered are trees, although extension to doubly linked lists and trees with upward pointers is hinted at.