Question: Transitive closure and path following as in kleene algebras

[boggle]

Hi, I was looking at kleene algebras recently. They naturally include a transitive closure operator. While it is possible to interpret the graph algebra under transitive closure semantics, is there a particular reason why a transitive closure operator was not included? Also, overlay corresponds to "+" in kleene algebras but "connect" is different. How hard/easy would it be to define kleene algebra "." in terms of graph algebra? "Connecting paths" seems a reasonable operation. What are reasons to have or not have it? Just a little curious about the background, I believe @snowleopard mentioned looking at kleene algebras in a blog post.

[snowleopard]

is there a particular reason why a transitive closure operator was not included?

Yes, it is indeed possible to include it, but I haven't had a chance to study the resulting algebraic structure. Note that there is an implementation of the transitive closure for edge-labelled graphs.

How hard/easy would it be to define kleene algebra "." in terms of graph algebra?

Here is one possible implementation for algebraic graphs without labels. It's interesting because it uses biclique to achieve compact representation for the resulting graph. There are a few other interesting implementations, but I haven't yet managed to implement or describe them properly. I hope to do this soon.

"Connecting paths" seems a reasonable operation. What are reasons to have or not have it?

Absolutely, this is a very natural notion, however vertex + overlay + compose are not sufficient for constructing graphs, because there is no way to create any edges. This was my main motivation for using the connect operation: vertex + overlay + connect gives you a minimalistic algebraic structure capable of describing any graph.

Is vertex + overlay + connect + compose an interesting algebra? It surely is! But it's also more complex.

Happy to keep this issue open for discussing relations with various Kleene algebras.