Algebraic structures for transitive closure

AbstractClosed semi-rings and the closure of matrices over closed semi-rings are defined and studied. Closed semi-rings are structures weaker than the structures studied by Conway [3] and Aho, Hopcroft and Ullman [1]. Examples of closed semi-rings and closure operations are given, including the case of semi-rings on which the closure of an element is not always defined. Two algorithms are proved to compute the closure of a matrix over any closed semi-ring; the first one based on Gauss–Jordan elimination is a generalization of algorithms by Warshall, Floyd and Kleene; the second one based on Gauss elimination has been studied by Tarjan [11, 12], from the complexity point of view in a slightly different framework. Simple semi-rings, where the closure operation for elements is trivial, are defined and it is shown that the closure of an n × n-matrix over a simple semi-ring is the sum of its powers of degree less than n. Dijkstra semi-rings are defined and it is shown that the rows of the closure of a matrix over a Dijkstra semi-ring, can be computed by a generalized version of Dijkstra's algorithm