Lehmann, D. J. (1976) Algebraic structures for transitive closure. Coventry, UK: Department of Computer Science..

Abstract

Closed semi-rings and the closure of matrices oven closed semirings are defined and studied. Closed semirings are structures weaker than the structunes studied by Conway [3] and Aho, Hopcnoft and Ullman [1]. Examples of closed semi-rings and closure operations are given, including the case of semirings on which the closure of an element is not always defined. Two algorithms are proved to compute the closure of a matrix oven any closed semiring; 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] and [12], from the complexity point of view in a slightly different framework. Simple semirings, where the closure operation for elements is trivial are defined and it is shown that the closure of an $n \times n$ matrix over a simple semiring is the sum of its powers of degree less than $ n$. Dijkstna sernirings are defined and it is shown that the rows of the closure of a matrix over a Dijkstra semiring, can he computed by a generalized version of Dijkstra algorithm.

Request changes to a record

Actions (login required)

View Item