Publication details
Optimal free binary decision diagrams for computation of EAR(n)
| Authors | |
|---|---|
| Year of publication | 2002 |
| Type | Article in Periodical |
| Magazine / Source | MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2002 |
| Citation | |
| Description | Ree binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with a constraint (additional to binary decision diagrams) that each variable is tested during the computation at most once. The function EAR, is a Boolean function on n x n Boolean matrices; EAR(n)(M) = 1 iff the matrix M contains two equal adjacent rows. We prove that the size of optimal FBDDs computing EARn is 2(theta)(log(2) n) |