next up previous
Next: ASAP structures Up: Related Work Previous: Graph Types

Group based fields

Group based fields [8] aims to extend data types to values indexed using a group. Here the directions from a node to a destination node are the generators of the group, the node in direction d from node n is described by the group element n.d. Much of the discussion centres on abelian groups which are very similar to arrays, particularly in the kinds of parallelisation that can be applied to them. More general groups are defined using a finite presentation , a list of words describing the equality between two particular words, which is extended to the rest of the group. In general the solution of the word problem for a group is an undecidable problem. This makes the idea of analysing programs over such structures intractable, since deciding if two explicitly given nodes are the same is not generally possible. When static analysis is your goal it makes sense to restrict the structures to ones with a unique normal form. It should be mentioned that the group itself is quite a specialised concept, for example all directions must have inverses, which would exclude one way directed graphs.


next up previous
Next: ASAP structures Up: Related Work Previous: Graph Types
Timothy Lewis
11/12/1997