References

@article{Jankovi\'{c}2000193,

title = {Lower bound sifting for MDDs},

author = {Dragan Jankovi\'{c} and Wolfgang G\"{u}nther and Rolf Drechsler},

url = {https://www.scopus.com/inward/record.uri?eid=2-s2.0-0033724305\&doi=10.1109%2fISMVL.2000.848619\&partnerID=40\&md5=40476e8421decf136522edca0e24c938},

doi = {10.1109/ISMVL.2000.848619},

year  = {2000},

date = {2000-01-01},

journal = {Proceedings of The International Symposium on Multiple-Valued Logic},

pages = {193 \textendash 198},

abstract = {Decision Diagrams (DDs) are a data structure for the representation and manipulation of discrete logic functions often applied in VLSI CAD. Common DDs to represent Boolean functions are Binary Decision Diagrams (BDDs). Multiple-valued logic functions can be represented by Multiple-valued Decision Diagrams (MDDs). The efficiency of a DD representation strongly depends on the variable ordering; the size may vary from linear to exponential. Finding a good ordering is an NP-hard problem that has received considerable attention resulting in many minimization methods. Sifting is the most popular heuristic for dynamic DD minimization. In this paper we give lower bounds for sifting of MDDs. Based on them, both lower bound sifting for MDD minimization and lower bound group sifting for BDD minimization are proposed. By the computation of good lower bounds large parts of the search space can be pruned resulting in very fast computations. This is demonstrated by experimental results.},

keywords = {Algorithms; Boolean functions; Computational complexity; Decision theory; Graph theory; Many valued logics; Theorem proving; Binary decision diagrams; Discrete logic functions; Lower bound sifting; Multiple valued decision diagrams; Multiple valued logic functions; Data structures},

pubstate = {published},

tppubtype = {article}

}