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

Xuanxiang Huang, Kehang Fang, Liangda Fang, Qingliang Chen, Zhao-Rong Lai, Linfeng Wei

AAAI 2019 pp. 2867-2875

doi:10.1609/AAAI.V33I01.33012867 /aaai/2019/huang2019aaai-bi/

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.

PDF AAAI Semantic Scholar

Cite

Text

Huang et al. "Bi-Kronecker Functional Decision Diagrams: A Novel Canonical Representation of Boolean Functions." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33012867

Markdown

[Huang et al. "Bi-Kronecker Functional Decision Diagrams: A Novel Canonical Representation of Boolean Functions." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/huang2019aaai-bi/) doi:10.1609/AAAI.V33I01.33012867

BibTeX

@inproceedings{huang2019aaai-bi,
  title     = {{Bi-Kronecker Functional Decision Diagrams: A Novel Canonical Representation of Boolean Functions}},
  author    = {Huang, Xuanxiang and Fang, Kehang and Fang, Liangda and Chen, Qingliang and Lai, Zhao-Rong and Wei, Linfeng},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {2867-2875},
  doi       = {10.1609/AAAI.V33I01.33012867},
  url       = {https://mlanthology.org/aaai/2019/huang2019aaai-bi/}
}