Free binary decision diagrams for the computation of EAR n期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Free binary decision diagrams for the computation of EAR n

Authors:	Jan Kára Daniel Král’

Affiliation:	(1) 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

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 EAR_n is the following Boolean function defined for n × n Boolean matrices: EAR_n(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.63log ^{2}_{2} n - O(log nlog log n)}}$ and we present a construction of such diagrams of size approximately $2^{{1.89log ^{2}_{2} n + O(log n)}}$ .

Keywords:	Binary decision diagrams free binary decision diagrams Boolean functions
本文献已被 SpringerLink 等数据库收录！