Tom Van Dijk, Robert Wille, Robert Meolic,
"Tagged BDDs: Combining Reduction Rules from Different Decision Diagram Types"
: International Conference on Formal Methods in CAD (FMCAD), 2017
Original Titel:
Tagged BDDs: Combining Reduction Rules from Different Decision Diagram Types
Sprache des Titels:
Englisch
Original Buchtitel:
International Conference on Formal Methods in CAD (FMCAD)
Original Kurzfassung:
Binary decision diagrams are fundamental data
structures in discrete mathematics, electrical engineering and
computer science. Many different variations of binary decision
diagrams exist, in particular variations that employ different
reduction rules. For some applications, such as on-the-fly state
space exploration, multiple reduction rules are beneficial to
minimize the size of the involved graphs. We propose tagged
binary decision diagrams, an edge-based approach that allows to
use two reduction rules simultaneously. Experimental evaluations
demonstrate that on-the-fly state space exploration is an order
of magnitude faster using tagged binary decision diagrams
compared to traditional binary decision diagrams.
Forschungs-