5 ms·

In particular, you can also endow graphs with lattice structures, which yields a bunch of of nice monotonicity/fixed-point/ordering theorems over graphs; comput

by 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.

by LolWolf 10y ago

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.