caa a22 4500 46790958X CHVBK 20180406152845.0 cr unu---uuuuu 170328e20060501xx s 000 0 eng 10.1007/s00037-006-0206-5 doi (NATIONALLICENCE)springer-10.1007/s00037-006-0206-5 Free binary decision diagrams for the computation of EAR n [Elektronische Daten] [Jan Kára, Daniel Král'] Abstract.: 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 × n Boolean matrices: EARn(M) = 1 iff the matrix M contains two equal adjacent rows. We prove that each FBDD computing EARn has size at least $$ 2^{{0.63\log ^{2}_{2} n - O(\log n\log \log n)}} $$ and we present a construction of such diagrams of size approximately $$ 2^{{1.89\log ^{2}_{2} n + O(\log n)}} $$ . Birkhäuser Verlag, Basel, 2006 Binary decision diagrams nationallicence free binary decision diagrams nationallicence Boolean functions nationallicence 94C10 nationallicence Kára Jan Department of Applied Mathematics and Institute for Theoretical Computer Science, Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, 118 00, Prague 1, Czech Republic aut Král' Daniel Department of Applied Mathematics and Institute for Theoretical Computer Science, Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, 118 00, Prague 1, Czech Republic aut computational complexity Birkhäuser-Verlag; www.birkhauser.ch 15/1(2006-05-01), 40-61 1016-3328 15:1<40 2006 15 37 https://doi.org/10.1007/s00037-006-0206-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-006-0206-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kára Jan Department of Applied Mathematics and Institute for Theoretical Computer Science, Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, 118 00, Prague 1, Czech Republic aut NATIONALLICENCE 700 1- Král' Daniel Department of Applied Mathematics and Institute for Theoretical Computer Science, Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, 118 00, Prague 1, Czech Republic aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhauser.ch 15/1(2006-05-01), 40-61 1016-3328 15:1<40 2006 15 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer