Algebraic structures for transitive closure
Lehmann, D. J. (1976) Algebraic structures for transitive closure. Coventry, UK: Department of Computer Science..Full text not available from this repository.
Official URL: http://eprints.dcs.warwick.ac.uk/1133/1/cs-rr-010....
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  and Aho, Hopcnoft and Ullman . 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  and , 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.
|Subjects:||Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science)|
|Divisions:||Faculty of Science > Computer Science|
|Publisher:||Department of Computer Science|
|Place of Publication:||Coventry, UK|
|Institution:||University of Warwick|
|Theses Department:||Department of Computer Science|
|Status:||Not Peer Reviewed|
|Access rights to Published version:||Open Access|
Actions (login required)