Publication details
Free binary decision diagrams for the computation of EAR(n)
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | COMPUTATIONAL COMPLEXITY |
| Citation | |
| Doi | http://dx.doi.org/10.1007/s00037-006-0206-5 |
| Keywords | binary decision diagrams; free binary decision diagrams; Boolean functions |
| Description | Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with the constraint (additional to binary decision diagram) that each variable is tested at most once during the computation. The function EARn is the following Boolean function defined for n x n Boolean matrices: EARn (M) = 1 iff the matrix M contains two equal adjacent rows. We prove that each FBDD computing EAR(n) has size at least 2(0.63log22n-O(log n log log n)) and we present a construction of such diagrams of size approximately 2(1.89 log22 n+O(log n)). |