![Důležité termíny](https://cdn.muni.cz/media/3633704/image_2.jpg?mode=crop¢er=0.5,0.5&rnd=133572412150000000&heightratio=0.5&width=278)
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) |