Lehmann, Daniel (1976) Algebraic structures for transitive closure. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)

Preview

Text WRAP_Lehmann_cs-rr-010.pdf - Published Version Download (1369Kb) | Preview

Request Changes to record.

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 x 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.

Item Type:	Report
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH):	Semirings (Mathematics), Closure operators
Series Name:	Theory of Computation Report
Publisher:	University of Warwick. Department of Computer Science
Official Date:	February 1976
Dates:	Date Event February 1976 ["eprint_fieldopt_dates_date_type_available" not defined]
Number:	Number 10
Number of Pages:	32
DOI:	CS-RR-010
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Status:	Not Peer Reviewed
Publication Status:	Unpublished
Reuse Statement (publisher, data, author rights):	D.J. Lehmann, Algebraic Structures for Transitive Closure, Theoretical Computer Science 4 (1), pp. 59-76 (1977)
Access rights to Published version:	Open Access (Creative Commons)
Date of first compliant deposit:	1 August 2016
Date of first compliant Open Access:	1 August 2016
Version or Related Resource:	Lehmann, D.J. (1977). Algebraic structures for transitive closure, Theoretical Computer Science, 4(1), pp. 59-76.

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads