Dec. Jan. 2018 Feb.
SunMonTueWedThuFriSat
31010203040506
07080910111213
14 151617181920
21222324252627
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".