I've done some work which made me appreciate the view that labelled hypergraphs are one of the most widely appropriate, general ways to represent data on stateful machines. In computer science, we commonly want to divide up state into a number of possibly overlapping data structures, which will contain and be referenced by pointers.
This lends itself to the following representation: data structures are hyperedges. Non-pointer data within data structures are labels of the associated hyperedge. And pointers are represented by vertices, possibly (not always!) needing an attribute to indicate which hyperedge is the source and which is the target of the pointer. Computation, then, is graph rewriting.
As Qiaochu says, hyperedges are absurdly general. Likewise, the notion of data. To make this useful, one needs to constrain the form the hyperedges take. What is nice is that the need to constrain the way that state is represented is perfectly matched with the need in useful programming langauges to contrain the representation of data, and furthermore, one can often cleanly map the programming-driven constraints into reasonable constraints on the hypergraphs.
The idea crops up again and again the literature on graph transformations. A good stepping off point is Drewes, Habel, & Kreowski, 1997, Hyperedge Replacement Graph Grammars, In Rozenberg, Handbook of Graph Grammars and Computing by Graph Transformations.
No comments:
Post a Comment