Complexity of monotone networks for Boolean matrix product
Paterson, Michael S. (1974) Complexity of monotone networks for Boolean matrix product. Coventry, UK: Department of Computer Science..Full text not available from this repository.
Official URL: http://eprints.dcs.warwick.ac.uk/1125/1/cs-rr-002....
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 \times K$ and $K\times 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.
|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)