Mar. Apr. 2018 May
SunMonTueWedThuFriSat
01020304050607
08091011121314
15 16 17 18 19 2021
22232425262728
29300102030405
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".