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 during the computation at most once. The function EAR n  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 EAR n  is 2 θ(log2  n) .
['Jan Kára', 'Daniel Král']
Optimal free binary decision diagrams for computation of EARn