2 sp

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 Qiachu 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, likewise, programming languages must constrain the way they represent state, and one can often cleanly map the programming-driven constraints into reasonable constraints on the hypergraphs.

The idea crops up again and in 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.

1

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 Qiachu 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, likewise, programming languages must constrain the way they represent state, and one can often cleanly map the programming-driven constraints into reasonable constraints on the hypergraphs.

The idea crops up again and in 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.