4 ms·

This is very interesting, but not all that surprising to me. Graphs are closely related to binary relations (on a single set). We can build a binary relation R

This is very interesting, but not all that surprising to me. Graphs are closely related to binary relations (on a single set). We can build a binary relation R such that x R y iff there is a directed edge from vertex x to vertex y. It is well known that that the binary relations with the union as the addition, and relational composition (the arrow in the article) as multiplication form an idempotent semiring. If define another unary operation as the reflexive transitive closure of a binary relation (adding a directed edge from a vertex to each reachable vertex) we even form a Kleene algebra, which allows to reason about graphs in terms of regular expressions and regular sets. Another interesting way to represent directed graphs is using matrices over boolean matrices (also forming an idempotent semiring). Matrices over min, + algebra (also a Kleene algebra) allow us to represent direct graphs with weighted edges and allow us to derive many interesting algorithms, such as the Floyd-Warshall (if we replace the min, + algebra by regular sets we get Kleene's algorithm instead).

LolWolf 10y ago
In particular, you can also endow graphs with lattice structures, which yields a bunch of of nice monotonicity/fixed-point/ordering theorems over graphs; computability/hardness of these properties touches some parts of my research areas. I do have a bit of a problem representing arbitrary graphs as matrices since it requires that each graph you're working with be a subgraph of some 'parent graph,' which is where I think this algebra shines since you're allowed to construct arbitrary graphs without much mathematical yoga.[1] Do you have any references/articles you find particularly interesting in the subjects you mentioned? I'd love to have a bit more in my reading list about it. ------ [1] That isn't to say that I'm discounting super useful things like Smith Normal form, etc.; just that they serve a different purpose than what I believe this article is trying to get at.
- solidangle 10y ago
  Yes! Graphs have many interesting algebraic properties. I'm not aware of articles treating graphs as Kleene algebras (I haven't looked for them though). Conway's "Regular Algebra and Finite Machines" [1] and Kozen's "A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events" [2] are interesting texts to read on Kleene algebra. [1] https://www.amazon.com/Regular-Algebra-Finite-Machines-Mathematics/dp/0486485838 https://www.amazon.com/Regular-Algebra-Finite-Machines-Mathe... [2] https://www.cs.cornell.edu/~kozen/papers/ka.pdf https://www.cs.cornell.edu/~kozen/papers/ka.pdf
  - LolWolf 10y ago
    Great, thanks!
  - sn0wleopard 10y ago
    solidangle: Indeed, there are a lot of graph algebras out there, and I looked at many of them, including the Kleene Algebras. So far I haven't found any algebra with the decomposition axiom, but if you come across one, please let me know! Why do I need the decomposition axiom? I haven't actually provided a motivation for it (or why I defined overlay and connect the way I did). So, here it is: just like LolWolf, I wanted to represent arbitrary graphs and only graphs using expressions, so expression x -> y -> z should be just a graph, and therefore I should be able to construct it from smaller pieces. But what should these pieces be? We can't make it equal to x -> y + y -> z because then our definition of -> would be partial, since it's not always possible to find 'the last node' (in this case y) that we need to connect to z (e.g. the left-hand side may be a cycle). The only choice that seems to work is to connect all vertices on the left-hand side to all vertices on the right hand side, which leads directly to the decomposition axiom.
solidangle 10y ago
I can no longer edit my post, but I just noticed that the arrow is different from relational composition. The semiring in my post is still interesting for graphs though, especially for reachability.

LolWolf 10y ago

In particular, you can also endow graphs with lattice structures, which yields a bunch of of nice monotonicity/fixed-point/ordering theorems over graphs; computability/hardness of these properties touches some parts of my research areas. I do have a bit of a problem representing arbitrary graphs as matrices since it requires that each graph you're working with be a subgraph of some 'parent graph,' which is where I think this algebra shines since you're allowed to construct arbitrary graphs without much mathematical yoga.[1] Do you have any references/articles you find particularly interesting in the subjects you mentioned? I'd love to have a bit more in my reading list about it. ------ [1] That isn't to say that I'm discounting super useful things like Smith Normal form, etc.; just that they serve a different purpose than what I believe this article is trying to get at.

solidangle 10y ago
Yes! Graphs have many interesting algebraic properties. I'm not aware of articles treating graphs as Kleene algebras (I haven't looked for them though). Conway's "Regular Algebra and Finite Machines" [1] and Kozen's "A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events" [2] are interesting texts to read on Kleene algebra. [1] https://www.amazon.com/Regular-Algebra-Finite-Machines-Mathematics/dp/0486485838 https://www.amazon.com/Regular-Algebra-Finite-Machines-Mathe... [2] https://www.cs.cornell.edu/~kozen/papers/ka.pdf https://www.cs.cornell.edu/~kozen/papers/ka.pdf
- LolWolf 10y ago
  Great, thanks!
- sn0wleopard 10y ago
  solidangle: Indeed, there are a lot of graph algebras out there, and I looked at many of them, including the Kleene Algebras. So far I haven't found any algebra with the decomposition axiom, but if you come across one, please let me know! Why do I need the decomposition axiom? I haven't actually provided a motivation for it (or why I defined overlay and connect the way I did). So, here it is: just like LolWolf, I wanted to represent arbitrary graphs and only graphs using expressions, so expression x -> y -> z should be just a graph, and therefore I should be able to construct it from smaller pieces. But what should these pieces be? We can't make it equal to x -> y + y -> z because then our definition of -> would be partial, since it's not always possible to find 'the last node' (in this case y) that we need to connect to z (e.g. the left-hand side may be a cycle). The only choice that seems to work is to connect all vertices on the left-hand side to all vertices on the right hand side, which leads directly to the decomposition axiom.

solidangle 10y ago

I can no longer edit my post, but I just noticed that the arrow is different from relational composition. The semiring in my post is still interesting for graphs though, especially for reachability.