Paterson, Michael S. (1974) Complexity of monotone networks for Boolean matrix product. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)

Preview

Text WRAP_Paterson_cs-rr-002.pdf - Published Version Download (688Kb) | Preview

Abstract

Any computation of Boolean matrix product by an acyclic network
using only the operations of binary conjunction and disjunction
requires at least IJK conjunctions and IJ(K-1) disjunctions for the
product of matrices of sizes I x K and K x J. Furthermore any two
such networks having these minimum numbers of operations are equivalent
using only the commutativity of both operations and the associativity
of disjunction.

Item Type:	Report
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH):	Matrices
Series Name:	Theory of Computation Report
Publisher:	University of Warwick. Department of Computer Science
Official Date:	July 1974
Dates:	Date Event July 1974 ["eprint_fieldopt_dates_date_type_available" not defined]
Number:	Number 2
Number of Pages:	14
Identification Number:	CS-RR-002
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Status:	Not Peer Reviewed
Publication Status:	Unpublished
Access rights to Published version:	Open Access
Version or Related Resource:	Paterson, M.S. (1975). Complexity of monotone networks for Boolean matrix product. Theoretical computer science, 1(1), pp.13-20.
URI:	http://wrap.warwick.ac.uk/id/eprint/46302

Request changes or add full text files to a record

Actions (login required)

View Item

Downloads