skip to main content
Language:
Search Limited to: Search Limited to: Resource type Show Results with: Show Results with: Search type Index

Novel Reduction Methods for Decision Diagrams

Access, IEEE, 2023, Vol.11, p.43592-43602

2013 IEEE ;DOI: 10.1109/ACCESS.2023.3266721

Full text available

Citations Cited by
  • Title:
    Novel Reduction Methods for Decision Diagrams
  • Author: Lucansky, Jan ; Kotuliak, Ivan
  • Subjects: Boolean functions ; Complexity theory ; Computer science ; decision diagrams ; KFDD ; MVDD ; Optimization methods ; Power demand ; residual variable
  • Is Part Of: Access, IEEE, 2023, Vol.11, p.43592-43602
  • Description: We propose a novel method of reduction for binary-based decision diagrams (DD) exploiting the similarities between Boolean functions. Conventional methods are able to remove redundant parts of DD that adhere to (or represent) identical structures. The proposed approach tries to take advantage of not only identical but also equivalent parts of a diagram, which produce identical results after a change in variable ordering. Basic types of DD, like Binary DD (BDD) or Functional DD (FDD) do not allow for the reduction of equivalent parts of a diagram as the notation of change in ordering would be lost. Therefore, we propose a new type of decision diagram able to incorporate different orders of variables and thus allowing the reduction of equivalent DD parts- Multi-Variable Decision Diagram (MVDD). The only remaining obstacle is the determination of equivalency, for which we also propose a new heuristic. The paper also presents reduction of Kronecker Functional DD (KFDD) and MVDD with regard to multiple parameters, where the optimization process relies heavily on evolutionary algorithms and Residual Variable (RV). The average added value of MVDD to the reduction of diagram size was 26.13% when compared to BDD and 12.27% when compared to KFDD while preserving similar values of power consumption and average path length in the diagram.
  • Publisher: IEEE
  • Language: English
  • Identifier: DOI: 10.1109/ACCESS.2023.3266721
  • Source: IEEE Open Access Journals
Back to results list
INSPIRE LIBRARY - TON DUC THANG UNIVERSITY (84-028) 37 755 057 Feedback
19 Nguyen Huu Tho St. Dist.7, HCM thuvien@tdtu.edu.vn

Copyright © 2017 INSPIRE LIBRARY - TON DUC THANG UNIVERSITY

Searching Remote Databases, Please Wait