English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Monotone Switching Circuits and Boolean Matrix Product

MPS-Authors
/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Galil,  Zvi
Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Mehlhorn, K., & Galil, Z. (1976). Monotone Switching Circuits and Boolean Matrix Product. Computing, 16, 99-111.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-AFB1-1
Abstract
We explore the concept of local transformations of monotone switching circuits, i.e. what kind of local changes in a network leave the input/output behavior invariant. We obtain several general theorems in this direction. We apply these results to boolean matrix product and prove that the school-method for matrix multiplication yields the unique monotone circuit.