Complexity of monotone networks for Boolean matrix product |
| |
Authors: | Michael S. Paterson |
| |
Affiliation: | Department of Computer Science, University of Warwick, Coventry, England |
| |
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×K and K×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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|