Tagged BDDs: Combining Reduction Rules from Different Decision Diagram Types. In International Conference on Formal Methods in CAD (FMCAD)
Sprache des Vortragstitels:
Englisch
Original Tagungtitel:
International Conference on Formal Methods in CAD (FMCAD)
Sprache des Tagungstitel:
Englisch
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-