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 |
| 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 |
Actions (login required)
 |
View Item |
