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

　　Speaker: Dr. Liangda Fang, Jinan University, Guangzhou (方良达，副教授，暨南大学，广州)

　　Venue: Seminar Room (Room 334), Building 5, Institute of Software, Chinese Academy of Sciences

　　Time: 15:00, June 25th, Tuesday, 2019

　　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.