Sep. Oct. 2018 Nov.
SunMonTueWedThuFriSat
300102 03040506
07080910111213
14151617181920
2122 2324252627
28293031010203
Click Seminar

TOPICS (Detail)

Publishing dayAugust 29, 2012 10:35:35 By shirai
Title

Counterexamples to the long-standing conjecture on the complexity of BDD

ContentWe disprove the long-standing conjecture, proposed by R.E. Bryant in 1986, that his binary decision diagram (BDD) algorithm computes any binary operation on two Boolean functions in linear time in the input–output sizes. See the details on the paper published in "Information Processing Letters".