On Optimizations of Edge-Valued MDDs for Fast Analysis of Multi-State Systems

• NAGAYAMA Shinobu

  Department of Computer and Network Engineering, Hiroshima City University

• SASAO Tsutomu

  Department of Computer Science, Meiji University

• BUTLER Jon T.

  Department of Electrical and Computer Engineering, Naval Postgraduate School

• THORNTON Mitchell A.

  Department of Computer Science and Engineering, Southern Methodist University

• MANIKAS Theodore W.

  Department of Computer Science and Engineering, Southern Methodist University

Abstract

In the optimization of decision diagrams, variable reordering approaches are often used to minimize the number of nodes. However, such approaches are less effective for analysis of multi-state systems given by monotone structure functions. Thus, in this paper, we propose algorithms to minimize the number of edges in an edge-valued multi-valued decision diagram (EVMDD) for fast analysis of multi-state systems. The proposed algorithms minimize the number of edges by grouping multi-valued variables into larger-valued variables. By grouping multi-valued variables, we can reduce the number of nodes as well. To show the effectiveness of the proposed algorithms, we compare the proposed algorithms with conventional optimization algorithms based on a variable reordering approach. Experimental results show that the proposed algorithms reduce the number of edges by up to 15% and the number of nodes by up to 47%, compared to the conventional ones. This results in a speed-up of the analysis of multi-state systems by about three times.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E97.D (9), 2234-2242, 2014

  The Institute of Electronics, Information and Communication Engineers

Keywords

• minimization algorithm of the number of edges
• EVMDDs
• grouping variables for optimization of decision diagrams
• multi-state systems
• system analysis using decision diagrams

Details

• CRID: 1390001204379683072
• NII Article ID: 130004685463
• DOI: 10.1587/transinf.2013lop0011
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E97.D/9/E97.D_2013LOP0011/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed