2 ms·
Haven't seen this notation in text books so far, but I guess one of the following 3 things happened: (1) The notation a->b was defined as a simple shorthand, i
by vog 10y ago
Haven't seen this notation in text books so far, but I guess one of the following 3 things happened:
(1) The notation a->b was defined as a simple shorthand, i.e. a->b := (a,b).
(2) The notation a->b was defined to be the graph consisting of just a, b and the edge, i.e. a->b := ({a,b}, {(a,b)}) ... this may be followed by some algebraic rules about how to combine small graphs to build larger graphs.
(3) The notation a->b may be a somewhat misused notation for functions, meaning the only possible function from set {a} to set {b}, i.e. the function that maps a to b. If you define a function to be a relation (i.e. a set of pairs) where the first elements are unique, then this is acually equal to {(a,b)}, i.e. the set containing exactly this one pair.
Interpretation (3) might look somewhat contrieved, but it actually isn't that much of a stretch, given the connections between graph theory and function structures through category theory.
- YeGoblynQueenne 10y agoI believe it's (1) and I think it might originate in Judea Pearl's textbook on causality [1], particularly the section on the IC algorithm. I've also encountered it in a bunch of papers on graph reconstruction, by Wermuth, Lauritzen, Spirtes and Glymour (not all in one go, I don't think). For instance, see [2]. I guess it's convenient notation for a typical step in those algorithms, where two edges are oriented towards a common vertex- shown as A -> B <- C or similar. That's a little more concise than {(A,B),(C,B)} but also more intuitive when the intention is to show how to (re)construct a graph from dependence relations, as those algorithms usually do. ___________________ [1] Causality; models, reasoning and inference: http://bayes.cs.ucla.edu/BOOK-2K/ http://bayes.cs.ucla.edu/BOOK-2K/ [2] A Fast Algorithm for Discovering Sparse Causal Graphs; Peter Spirtes & Clark Glymour: http://repository.cmu.edu/cgi/viewcontent.cgi?article=1316&context=philosophy http://repository.cmu.edu/cgi/viewcontent.cgi?article=1316&c...