The Library
Complexity of monotone networks for Boolean matrix product
Tools
Tools
Tools
Paterson, Michael S. (1974) Complexity of monotone networks for Boolean matrix product. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)
|
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 |
| 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 |
