A mathematical structure associated with transitive closure: does this have a name?

Ecosystem
5

The mathematical structure you’re looking for is Kleene Algebra, the algebra of regular expressions.
A Kleene Algebra is an idempotent semiring with an iteration operator, usually denoted as *.

Dexter Kozen’s lecture notes on Kleene Algebra explain the connection to all-pairs shortest paths. The semiring in that case is the “tropical semiring”, the Kleene Algebra is simply called min,+ Kleene Algebra.

Here is a paper that is dedicated to this connection (though I haven’t read it myself).

EDIT: Let me say briefly how the structure you observed map to Kleene Algebra – see the sources linked above for more details:

  1. Label on edges → n-by-n matrix over label set K, where the label set forms a Kleene Algebra (K, 0, 1, +, x, *), n is the number of vertices, and M_i,j = label on edge from i to j (0 if there is no edge).
  2. Composing labels → x (not +) from the Kleene Algebra K
  3. Selecting labels → + from the Kleene Algebra
  4. One iteration of the algorithm → matrix multiplication
  5. Taking the transitive closure → * from the Kleene Algebra K^nxn – if K is a Kleene Algebra, so is the set K^nxn of n-by-n matrices over K
6 Likes