Bi-Kronecker Functional Decision Diagrams: A Novel Canonical Representation of Boolean Functions

  • Xuanxiang Huang Jinan University
  • Kehang Fang Jinan University
  • Liangda Fang Jinan University
  • Qingliang Chen Beijing University of Posts and Telecommunications
  • Zhao-Rong Lai Jinan University
  • Linfeng Wei Jinan University


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.

AAAI Technical Track: Knowledge Representation and Reasoning