Informace o publikaci
Optimal free binary decision diagrams for computation of EAR(n)
| Autoři | |
|---|---|
| Rok publikování | 2002 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2002 |
| Citace | |
| Popis | 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) |