Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-061 | 29th August 2003 00:00

Free Binary Decision Diagrams for Computation of EAR_n

RSS-Feed




TR03-061
Authors: Jan Kára, Daniel Král
Publication: 8th September 2003 18:22
Downloads: 934
Keywords: 


Abstract:

Free 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 at most once during the computation. The function EAR_n is the following Boolean function defined
for n x n Boolean matrices: EAR_n(M)=1 iff the matrix M contains two equal adjacent rows. We prove that each FBDD computing EAR_n must have size
at least 2^{0.63 log_2^2 n-O(log n loglog n)} and we present a construction of such diagrams of size 2^{1.89 log_2^2 n+O(log n)}.



ISSN 1433-8092 | Imprint