Bi-Kronecker Functional Decision Diagrams: A Novel Canonical Representation of Boolean Functions - Huang, Xuanxiang; Fang, Kehang; Fang, Liangda; Chen, Qingliang; Lai, Zhao-Rong; Wei, Linfeng (Proceedings of the AAAI Conference on Artificial Intelligence, 2019)
In this paper, we present a novel data structure for compact representation and effective manipulations of Boolean functions, called Bi-Kronecker Functional Decision Diagrams (BKFDDs). BKFDDs integrate the classical expansions (the Shannon and Davio expansions) and their bi-versions. Thus, BKFDDs are the generalizations of existing decision diagrams: BDDs, FDDs, KFDDs and BBDDs. Interestingly, under certain conditions, it is sufficient to consider the above expansions (the classical expansions and their bi-versions). By imposing reduction and ordering rules, BKFDDs are compact and canonical forms of Boolean functions. The experimental results demonstrate that BKFDDs outperform other existing decision diagrams in terms of sizes.