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

Authors

  • 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

DOI:

https://doi.org/10.1609/aaai.v33i01.33012867

Abstract

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.

Downloads

Published

2019-07-17

How to Cite

Huang, X., Fang, K., Fang, L., Chen, Q., Lai, Z.-R., & Wei, L. (2019). Bi-Kronecker Functional Decision Diagrams: A Novel Canonical Representation of Boolean Functions. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2867-2875. https://doi.org/10.1609/aaai.v33i01.33012867

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning