Tagged BDDs: Combining reduction rules from different decision diagram types

Tom Van Dijk, Robert Wille, Robert Meolic

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

19 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 17th Conference on Formal Methods in Computer-Aided Design, FMCAD 2017
EditorsGeorg Weissenbacher, Daryl Stewart
PublisherIEEE
Pages108-115
Number of pages8
ISBN (Electronic)9780983567875
DOIs
Publication statusPublished - 8 Nov 2017
Externally publishedYes
Event17th Conference on Formal Methods in Computer-Aided Design, FMCAD 2017 - Vienna, Austria
Duration: 2 Oct 20176 Oct 2017
Conference number: 17

Conference

Conference17th Conference on Formal Methods in Computer-Aided Design, FMCAD 2017
Abbreviated titleFMCAD 2017
Country/TerritoryAustria
CityVienna
Period2/10/176/10/17

Keywords

  • n/a OA procedure

Fingerprint

Dive into the research topics of 'Tagged BDDs: Combining reduction rules from different decision diagram types'. Together they form a unique fingerprint.

Cite this